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>.
== Источники информации ==
