108
правок
Изменения
Нет описания правки
<tex>O(s + t)</tex> (время подсчета <tex>\pi()</tex> для <tex>P</tex>) + <tex>O(s)</tex> (последующий <tex>for</tex>) <tex>= O(s + t)</tex>.
*'''Оценка по памяти'''
Предложенная реализация имеет оценку по памяти <tex>O(S+T)</tex>. Оценки <tex>O(S)</tex> можно добиться за счет не запоминания значений <tex>\pi()</tex> для позиций в <tex>P</tex> меньших <tex>t + 1</tex> (т.е. до начала цепочки <tex>S</tex>)
