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

Также существуют другие решения, дающие лучший результат для небольших k и требующие O(n(1 + k4/m)) времени [ ]. Для случая расстояния Хэмминга можно получить лучший результат при использовании сверток [1].

Теорема 5 (Амир и др,. 2004 [ ]). Существует решение с временем выполнения O(npklogk) и O(n(1 + k3/m)logk) в наихудшем случае для задачи ASM с использованием расстояния Хэмминга.

Последний результат для расстояния редактирования [ ] демонстрирует время O(n) в случае, если k достаточно мало (k = O(m1/4)). Можно также получить время O(n) для расстояний редактирования с единичной стоимостью за счет экспоненциального дополнительного члена в m или k. Количество разных столбцов в матрице C не зависит от n, так что переход от одного возможного столбца к следующему может быть предварительно вычислен при помощи конечного автомата.

Теорема 6 (Укконен, 1985 [ ]). Существует решение с временем выполнения O(n + mmin(3m; m(2ma)k)) в наихудшем случае для задачи ASM с использованием расстояния редактирования.

Сложность задачи ASM в наихудшем случае, разумеется, составляет £?(n), однако неизвестно, может ли она быть достигнута для любых значений m и k. Впрочем, сложность этой задачи в среднем случае известна.

Теорема 7 (Чанг и Марр, 1994 [ ]). Существует решение с временем выполнения &(n(k + log^ m)/m) в среднем случае для задачи ASM с использованием расстояния редактирования с единичной стоимостью.