Изменения

Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур <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>s</tex> из <tex>\log m</tex> стадий анализа образца цикл <tex>for</tex> производит <tex>2^{s-1}</tex> итераций <tex>(2^{s-1} \leqslant i \leqslant 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>. Проведя суммирование по всем стадиям, получаем общее время счета <tex>O(\sum_{i=1}^{\log m} km)</tex> = <tex>O(km \log m)</tex>. Таким образом, общие затраты времени, включающие предварительную обработку образца и анализ текста, равны <tex>O(k(n + m \log m))</tex>.