使用主定理求解递推关系T(n)=2T(n/2)+n²的相关问题

问题1：你的计算过程是否正确 #

• 首先你的参数取值完全正确：递推式T(n) = 2T(n/2) + n²对应的a=2（子问题个数）、b=2（子问题规模缩放比例）、f(n)=n²（递归外的计算代价）
• 计算log_b a = log_2 2 =1，对应主定理的基准项为n^{log_b a} =n^1 =n
• 你套用主定理第三种情况的前提成立：f(n)=n² = Ω(n^{1+ε})，取ε=1即可满足要求
• 额外补充：主定理第三种情况还要求验证正则条件，即存在常数c<1，使得a f(n/b) ≤ c f(n)对足够大的n成立。代入数值验证：2*f(n/2) = 2*(n/2)² = n²/2 ≤ (1/2)f(n)，取c=1/2<1完全满足条件，因此你得出T(n) = Ω(n²)的结论是正确的。

问题2：如何得到Θ阶的结果 #

• 首先纠正一个概念误解：不存在「求解Θ(Ω(n²))」的说法，Θ阶的定义是同时满足同阶的上界(O)和下界(Ω)，你已经得到了下界Ω(n²)，只要再证明上界T(n)=O(n²)，就能推出T(n)=Θ(n²)。
• 两种方法可以得到Θ阶结果：
  • 方法1：直接套用主定理结论：只要满足第三种情况的所有条件（包括正则条件），主定理直接给出T(n)=Θ(f(n))，也就是T(n)=Θ(n²)，不需要额外单独计算上界。
  • 方法2：代入法验证上界：假设对所有小于n的k，有T(k) ≤ 2k²（2为待确定的常数），代入递推式可得：

    T(n) = 2T(n/2) +n² ≤ 2*2*(n/2)² +n² = 2*(n²/2) +n² = n² +n² =2n²
    边界条件比如T(1)=常数≤2*1²，显然成立，因此上界O(n²)成立，结合你已经得到的下界Ω(n²)，可推出T(n)=Θ(n²)。

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