46
правок
Изменения
Нет описания правки
(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n) = ... = 2kT2^kT(1) + kO(n).
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2k2^k=n</tex>, а значит <tex>k=log(n)</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ log(n)O(n)</tex>. Так как <tex>T(1)</tex> - константа, то <tex>T(n)=O(n)+log(n)O(n)=O(nlog(n))</tex>.
