Локальное выравнивание (с вогнутыми штрафами за гэп): различия между версиями

Миллер и Майерс провели некоторые эксперименты для сравнения своего алгоритма с алгоритмом Ватермана (Уотермана) с временем выполнения O(n3) [12] на ряде различных вогнутых штрафных функций. Для этих экспериментов были сгенерированы искусственные последовательности. Результаты экспериментов привели к предположению, что метод Ватермана выполняется  за время O(n3), когда две заданные строки очень похожи или оценка за различающиеся символы мала, тогда как алгоритму Миллера и Майера требуется время O(n2), если диапазон функции W(k) функционально не зависит от n.