Изменения

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

Декомпозиция Линдона

Нет изменений в размере, 21:17, 4 мая 2014
Асимптотика
Внешний цикл <tex>\mathrm{while}</tex> делает не более <tex>n</tex> итераций, поскольку в конце каждой его итерации <tex> i </tex> увеличивается как минимум на <tex> 1 </tex>. Второй внутренний цикл выполнится суммарно не более <tex> n </tex>, так он добавляет к ответу все символы, причём каждый символ лишь единожды.
Оценим теперь количество итераций первого вложенного цикла <tex>\mathrm{while}</tex>. Для этого рассмотрим второй вложенный цикл <tex>\mathrm{while}</tex> {{---}} он при каждом своём запуске выводит некоторое количество <tex>r \geqslant 1</tex> копий одной и той же простой строки некоторой длины <tex>p = j - k</tex>. Заметим, что строка <tex>s_2</tex> является предпростой, причём её простые строки имеют длину как раз <tex>p</tex>, т.е. её длина не превосходит <tex>r \cdot p + p - 1</tex>. Поскольку длина строки <tex>s_2</tex> равна <tex>j - i</tex>, а указатель <tex>j</tex> увеличивается по единице на единицу на каждой итерации первого вложенного цикла <tex>\mathrm{while}</tex>, то этот цикл выполнит не более <tex>r \cdot p + p - 2</tex> итераций. Худшим случаем является случай <tex>r = 1</tex>, и мы получаем, что первый вложенный цикл <tex>\mathrm{while}</tex> всякий раз выполняет не более <tex>2p - 2</tex> итераций. Вспоминая, что всего выводится <tex>n</tex> символов, получаем, что для вывода <tex>n</tex> символов требуется не более <tex>2n - 2</tex> итераций первого вложенного <tex>\mathrm{while}</tex>.
Итого получаем, что итоговая асимптотика алгоритма составляет <tex> O(n) </tex>.
Отметим, что алгоритму требуется <tex> O(1) </tex> памяти: на указатели <tex> i, j, k </tex>.
Анонимный участник

Навигация