Изменения

Перейти к: навигация, поиск
Время работы
При предподсчёте перебирается <tex> | \Sigma | ^k </tex> (где <tex> | \Sigma | </tex> — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по <tex> 2^{k - 1} </tex> битовых масок. Для самого предподсчёта требуется время <tex> O(k^2) </tex>. Дальнейший алгоритм поиска НОП требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>. Тогда суммарное время работы алгоритма составляет <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) </tex>.
Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём <tex> k </tex>, решив неравенство : <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} </tex>. Оно преобразуется к виду  <tex> \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 </tex>. Далее извлекаем корень:  <tex> \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n </tex>. Прологарифмируем:  <tex> k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n </tex>. Отсюда  Пренебрегая <tex> \log k </tex> и <tex> \log 2 </tex> как <tex> o(k ) < /tex>, получаем <tex> k \leqslant \frac{\log n}{1 + \log | \Sigma |}</tex>
== Источники ==
Анонимный участник

Навигация