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

我们可以使用归纳法来证明当 T(n) = 2T(n/2)+n, T(1) = 0 时， T(n) = nlog2(n)，假设 n 是 2 的指数倍。

基本情况：当 n = 1 时，T(1) = 0，nlog2(n) = 0，两者相等。

归纳假设：假设当 n = 2^k 时，T(n) = nlog2(n) 成立，其中 k 是非负整数。

归纳步骤：当 n = 2^(k+1) 时，

T(n) = 2T(n/2) + n

= 2T(2^k) + 2^(k+1)

= 2(2^k log2(2^k)) + 2^(k+1) （根据归纳假设，T(2^k) = 2^k log2(2^k)）

= 2^(k+1) k + 2^(k+1)

= 2^(k+1) (k+1)

= nlog2(n)

因此，当 T(n) = 2T(n/2)+n, T(1) = 0 时， T(n) = nlog2(n)，假设 n 是 2 的指数倍成立。