Изменения

Перейти к: навигация, поиск

Префикс-функция

65 байт убрано, 10:17, 13 июня 2012
Время работы
===Время работы===
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>while</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Из предыдущего утверждения, с учетом того что Поскольку внутри цикла <tex>while</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>while</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
Анонимный участник

Навигация