76
правок
Изменения
Нет описания правки
==Алгоритм==
===Оптимизация глубины рекурсии до O(logn) в худшем случае===
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>
Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>
<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>
<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)
===Среднее время работы===
