177
правок
Изменения
→Асимптотики
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m^2 + \sigma)</tex> времени и памяти.
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex > \Omega(\dfrac{n / }{m})</tex> сравнений.
'''Пример:'''
Исходный текст <tex>bb \dots bb</tex> и шаблон <tex>abab \dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m / }{2}</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>\dfrac{m / }{2}</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
