algorithm - 递归树法求解递归方程

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)