Метод дерева рекурсии для решения уравнения рекурсии

Question

Как решить рекуррентное соотношение - T (n) = 2T (n / 2) + nlogn, используя дерево рекурсии?

Answer 1

После расширения у нас будет:

T(n) = 2(2T(n/2^2) + n/2 log(n/2)) + nlog(n) = 2^2 T(n/2^2) + n log(n/2) + n log(n)
= 2^2(2T(n/2^3) + n/2^2 + log(n/2^2) 
= 2^3T(n/2^3) + nlog(n/2^2) + n log(n/2) + n log(n)

Следовательно, используя индукцию, мы будем иметь:

T(n) = n ( log(n) + log(n/2) + log(n/2^2) + ... + log(n/2^log(n)))
= n log(n * n/2 * n/2^2 * ... * n/2^log(n))
= n log(n^log(n) / 2^(1 + 2 + ... + log(n)))
= n log(n^log(n) / 2^(log(n)*(log(n)+1)/2)
= n log((n^2 / 2^(log(n)+1)) ^ (log(n)/2))
= n (log(n)/2) log(n^2 / 2n) = Theta(n (log(n))^2)