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

'''Теорема 8 (Фредриксон и Наварро, 2004 [6]). Существует оптимальное в среднем решение для задачи ASM с использованием расстояния редактирования для любого <math>k/m \le \frac{1 - e / \sqrt{\sigma}}{2 - e / \sqrt{\sigma}} = 1/2 - O(1 / \sqrt{\sigma})</math>'''  

Данный результат дословно применим и к indel-расстоянию. Для расстояния Хэмминга достигается та же сложность, однако граница на k/m улучшается до <math>1 - 1 / \sqrt{\sigma}</math>. Отметим, что при достижении предельного значения k/m средняя сложность уже составляет <math>\Theta(n)</math>. Неясно, для какого предела k/m можно получить среднее линейное время выполнения.