418
правок
Изменения
→Асимптотики
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m + \sigma)</tex> времени и памяти* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
В 1991 году Р.Коул доказал следующую теорему:
