Question

图中画波浪线的地方，这个[4^(k+1)]T(1)是怎么来的呢？如果成立，那如何知道n=2^(k+1)呢?

Answer 1

在这个问题中，[4^(k+1)]T(1)的推导来自于递归式中的通项公式。递归式是T(n) = 4T(n/2) + n^2，其中n是问题规模。我们可以使用递归展开的方法，将T(n)不断展开，直到得到T(1)为止。展开过程如下：
T(n) = 4T(n/2) + n^2
= 4[4T(n/4) + (n/2)^2] + n^2
= 4^2T(n/4) + 4(n/2)^2 + n^2
= 4^2T(n/4) + n^2/2^2 + n^2
= 4^2[4T(n/8) + (n/4)^2] + n^2/2^2 + n^2
= 4^3T(n/8) + 4(n/4)^2 + n^2/2^2 + n^2
= 4^3T(n/8) + n^2/2^3 + n^2/2^2 + n^2
...
继续展开可以得到：
T(n) = 4^(k+1)T(n/2^k) + n^2/2^k + n^2/2^(k-1) + ... + n^2/2^2 + n^2/2 + n^2
当n/2^k=1时，即n=2^k时，展开式的最后一项为n^2，其它项均为n^2/2^i，其中i从1到k-1，共有k-1项。将这些项相加，可以得到：
T(n) = 4^(k+1)T(1) + n^2[1/2^k + 1/2^(k-1) + ... + 1/2^2 + 1/2 + 1]
这里的n=2^k，因此可以将上式写成：
T(2^k) = 4^(k+1)T(1) + (2^k)^2[1/2^k + 1/2^(k-1) + ... + 1/2^2 + 1/2 + 1]
简化一下上式得：
T(2^k) = 4^(k+1)T(1) + 2^(2k)(2 - 1/2^k)
将上式中的k替换为log2(n)，可以得到：
T(n) = 4(log2n+1)T(1) + n^2(2 - 1/n)
因此，[4^(k+1)]T(1)就是递归式的通项公式，n=2^(k+1)则是通过将递归式不断展开，得到n=2^k的过程中推导出来的。