Последовательное приближенное сравнение строк: различия между версиями

Последовательное приближенное сравнение строк (посмотреть исходный код)

920 байт добавлено , 29 марта 2019

4551

правка

@@ Строка 85: / Строка 85: @@
 == Открытые вопросы ==
+Сложность задачи в наихудшем случае не вполне понятна. Для расстояния редактирования с единичной стоимостью она составляет <math>\Theta(n)</math> в случае, если <math>m = O(min(log \; n, (log_{\sigma} n)^2))</math> или <math>k = O(min(m^{1/4},log_{m \sigma} n))</math>. Для взвешенного расстояния редактирования сложность составляет <math>\Theta(n)</math> в случае <math>m = O(log_{\sigma} n)</math>. Неизвестно также, для какого значения k/m можно получить среднее время O(n); до настоящего момента его удавалось получить для <math>k/m = 1/2 - O(1 / \sqrt{\sigma})</math>.
+== Экспериментальные результаты ==