算法导论里用主方法计算时间复杂度的题

Question

递归式如下：T(n)=2T(n/2)+nlgn
用主方法求解T(n)。
没找到确切答案，所以来看看有没有大神可以解出来的。
大家可以再算法导论第三版P95找到这个问题。

Answer 1

$$a = 2, b = 2, f(n) = nlogn$$
$$因为 f(n) ∈ Θ(nlogn), k=1 可以用 case 2$$
$$所以 T(n) = Θ(nlog^2n)$$

参考 https://en.wikipedia.org/wiki...