# 二、请证明当 T(n) = 2T(n/2)+n, T(1) = 0 时， T(n) = nlog2(n), 假设 n 是 2 的指数倍

证明：

当 n=1 时，T(1) = 0，成立。

假设当 n=k 时，T(k) = klog2(k)，成立。

当 n=2k 时，

T(2k) = 2T(k) + 2k

= 2klog2(k) + 2k （根据假设）

= 2k(log2(k) + 1)

= 2klog2(2k)

因此，当 n=2k 时，T(n) = nlog2(n) 成立。

综上所述，当 T(n) = 2T(n/2)+n, T(1) = 0 时，T(n) = nlog2(n)，假设 n 是 2 的指数倍，得证。