297
правок
Изменения
→Оценка работы
Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур <tex>merge</tex> и <tex>extend</tex>, каждая из <tex>n-m+1</tex> итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время <tex>O(n)</tex>. Общее число операций, выполняемых процедурой <tex>extend</tex> во время вызовов равно <tex>O(n)</tex>, так как она проверяет каждый символ текста не больше одного раза. Процедура <tex>merge</tex> при каждом вызове обрабатывает вектора <tex>pm[i-r][1...2k+1]</tex> и <tex>tm[r][1...k+1]</tex>, которые в сумме имеют <tex>3k+2</tex> элементов. Время работы <tex>merge</tex> можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное <tex>O(k)</tex>. Таким образом, можно видеть, что общее время анализа текста составляет <tex>O(nk)</tex>.
Рассмотрим построение <tex>pm</tex>Используя аргументы, аналогичные применявшимся при проверке корректности процедуры merge, можно показать, что для нахождения требуемого количества несовпадений на стадии s требуется <tex>min\{2^{log(m)-s}4k+1, m-2^{s}\}</tex> позиций, для которых выполняется условие B, и в особом случае, а именно, на стадии <tex>\log m</tex>, требуется <tex>4k + 1</tex> таких позиций.
На каждой стадии <tex>s</tex> из <tex>\log m</tex> стадий анализа шаблона цикл <tex>for</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} < i < 2^{s}-1)</tex>. Если не считать время работы процедур <tex>merge</tex> и <tex>extend</tex>, каждая итерация требует фиксированного времени. Для всех итераций на шаге <tex>s</tex> процедуре <tex>extend</tex> требуется время <tex>O(m)</tex>. Ранее было показано, что время работы <tex>merge</tex> пропорционально числу искомых несовпадений. Таким образом, каждый вызов <tex>merge</tex> занимает время <tex>O(min\{2^{log(m)-s}4k+1, m-2^{s}\})</tex>, что равно <tex>O(2k2^{\log (m-s)})</tex>. Таким образом, общее время для стадии <tex>s</tex> равно <tex>O(m+2^{l-1}(2k2^{\log (m-s)}))</tex> = <tex>O(km)</tex>. Проведя суммирование по всем стадиям, получаем общее время счета (//todo). Таким образом, общие затраты времени, включающие предварительную обработку шаблона и анализ текста, равны <tex>O(k(n + m \log m)</tex>.
==Пример==
