102
правки
Изменения
Нет описания правки
Асимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <tex> O(n \log n) </tex> из рекурентного соотношения <tex>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [[Сортировка слиянием | сортировки слиянием]]).
Количество блоков в ответе также будет <tex> O(n \log n) </tex>: на каждом рекурсивном запуске при рассмотрении пересекающих повторов, которые пересекают границу раздела повторов , добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение <tex>M(n)=2M(n/2)+O(n)</tex>.
== См. также ==
