Работает ли алгоритм Левенштейна (Edit Distance) быстрее, чем O (n * m) в собственной базе данных графа?

Question

Будет ли у Левенштейна (Изменить расстояние) более сложная временная сложность в собственной базе данных графов, такой как Neo4j, чем текущий предел O (n * m)? Если так, то почему?

Answer 1

Поскольку реализации из apoc.text.levenshteinDistance и apoc.text.levenshteinSimilarity просто полагаются на org. apache .commons.text.simility.LevenshteinDistance для выполнения расчетов, APO * Библиотека 1019 * не вносит каких-либо улучшений сложности.

В любом случае при таком расчете следует просто сравнивать 2 строки текста и никоим образом не полагаться на графическую природу БД.

* 1010 И, наконец, было доказано , что сложность не может быть улучшена (если только гипотеза Сильного экспоненциального времени не верна).