Изменения

Перейти к: навигация, поиск
Время работы
==Время работы==
Проведем оценку асимптотики времени работы предложенного алгоритма. Посмотрим сколько нам потребуется действий на каждом шаге бинарного поиска. Во-первых, хеширование подстрок строки <tex>Ss</tex> и запись их в Set требует <tex>O(len(S)|s|)</tex> шагов. Во-вторых, хеширование подстрок строки <tex>Tt</tex> и проверка их наличия в Set требует <tex>O(len(T)|t|)</tex>. В приведенных рассуждениях предполагается, что операции записи в Set и проверка наличия элемента в Set работают за амортизированную <tex>O(1)</tex>. Поскольку хешировали с помощью [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа|этого]] метода, то это занимает линейное время. Значит,на каждый шаг бинарного поиска требуется <tex>O(max(len(S)|s|, len(T)|t|))</tex> действий. На самом деле требуется несколько больше времени, поскольку совпадение хешей не дает гарантии совпадения подстрок, однако чтобы это было справедливо с большой вероятностью, достаточно проверить совпадение лишь нескольких произвольных символов, вместо полной проверки. Тогда на это потребуется некоторое константное число операций, что маскируется с помощью <tex>O</tex>. Заметим, что всего для завершения бинарного поиска потребуется <tex>O(\log(\min(len(S)|s|, len(T)|t|)))</tex> шагов. Следовательно, суммарное время работы алгоритма будет <tex>O(\log(\min(len(S)|s|, len(T|t|))) * \times \max(len(S)|s|, len(T)|t|))</tex> действий. 
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
Анонимный участник

Навигация