如何用主定理与递归树求解递推式T(n)=4T(n/4)+n²？

嘿，我来帮你理清这个递推式的正确解法，你之前得到的两个结论里，递归树的结果应该是计算时出了小差错，咱们一步步来拆解：

首先回忆主定理的适用场景：对于形如 T(n) = aT(n/b) + f(n) 的递推式（其中 a≥1，b>1，f(n) 是渐近正函数），分三种情况判断：

• 情况1：如果 f(n) = O(n^(log_b a - ε))（ε>0），那么 T(n) = θ(n^(log_b a))
• 情况2：如果 f(n) = θ(n^(log_b a) log^k n)（k≥0），那么 T(n) = θ(n^(log_b a) log^(k+1) n)
• 情况3：如果 f(n) = Ω(n^(log_b a + ε))（ε>0），且满足正则条件：存在常数 k<1，使得对足够大的 n 有 a*f(n/b) ≤ k*f(n)，那么 T(n) = θ(f(n))

对应到你的递推式 T(n) = 4T(n/4) + n²：

• a=4，b=4，所以 log_b a = log₄4 = 1，对应的 n^(log_b a) = n^1 = n
• 非递归项 f(n)=n²，显然 n² 是 Ω(n^(1+ε))（比如取 ε=1 就满足）
• 验证正则条件：计算 a*f(n/b) = 4*f(n/4) = 4*(n/4)² = 4*(n²/16) = n²/4，显然 n²/4 ≤ (1/2)*n²（取 k=1/2<1），对所有 n≥1 都成立，满足正则条件

所以完全符合主定理的第三种情况，最终结论是 T(n) = θ(n²)。

咱们假设 n 是4的幂（即 n=4^k，k≥0，当 k=0 时 n=1，T(1)=c），把递归树逐层展开：

• 第0层（根节点）：对应递推式的非递归项，代价为 n²
• 第1层：有4个子节点，每个子节点的代价是 (n/4)²，总代价为 4*(n/4)² = n²/4
• 第2层：有 4²=16 个子节点，每个子节点的代价是 (n/4²)²，总代价为 16*(n/4²)² = n²/16
• ...
• 第k层：有 4^k = n 个子节点，每个子节点的代价是 T(1)=c，总代价为 n*c

现在把所有层的代价加起来：

T(n) = n² + n²/4 + n²/16 + ... + n²/(4^k) + n*c

前半部分是首项为 n²、公比为 1/4 的等比数列，项数为 k+1（k=log₄n）。等比数列求和公式为：

和 = 首项*(1 - 公比^(项数))/(1 - 公比)

代入数值后：

等比数列和 = n²*(1 - (1/4)^(log₄n + 1))/(1 - 1/4)

因为 (1/4)^(log₄n) = n^(-1)，所以 (1/4)^(log₄n +1) = 1/(4n)，代入后化简可得这部分的和是 θ(n²)。

最后一项 n*c 是 θ(n)，属于低阶项，不影响渐近复杂度。所以最终 T(n) = θ(n²)，和主定理的结论一致。

你之前得到的 θ(n² log₄n) 应该是误把每一层的代价当成了恒定的 n²，但实际上每一层的代价是按 1/4 的比例递减的，总和是收敛到常数倍的 n²，而非和层数相乘。

内容的提问来源于stack exchange，提问作者molamola