如何求解递推关系T(n) = 7T(n/2)+3n²+2的Big Theta记号

这个递推式是典型的分治类递推，直接用主定理即可快速求解，也可以用递推展开法验证结果，具体推导过程如下：

方法1：主定理求解 #

主定理适用的递推形式为 T(n) = aT(n/b) + f(n)，首先提取对应参数：

• 子问题数量 a = 7
• 子问题规模缩放系数 b = 2
• 单层计算开销 f(n) = 3n² + 2

步骤1：计算基准阶 #

先计算主定理的基准项：n^(log_b a) = n^(log₂7) ≈ n^2.807

步骤2：比对开销项和基准项的增长速度 #

f(n)的增长阶为Θ(n²)，显然n²的增长速度慢于n^2.807，符合主定理第一种判定规则：

若存在常数ε>0，使得f(n) = O(n^(log_b a - ε))，则T(n) = Θ(n^(log_b a))
此处取ε=0.8即可满足判定条件，3n² + 2 = O(n^(2.807-0.8)) = O(n^2.007)。

步骤3：得到最终结果 #

低阶项3n²和常数项2不会改变渐进复杂度的阶，因此最终结果为Θ(n^log₂7)，近似可写为Θ(n^2.81)。

方法2：递推展开验证 #

将递推式逐层展开：

1. 第一层：T(n) = 7T(n/2) + 3n² + 2
2. 第二层：T(n) = 7²T(n/2²) + 7*3*(n/2)² + 3n² + 7*2 + 2
3. 第k层：T(n) = 7^k T(n/2^k) + 3n² * Σ(i=0到k-1) (7/4)^i + 2 * Σ(i=0到k-1)7^i

当k=log₂n时，n/2^k=1，边界条件T(1)为常数，此时：

• 第一项7^k = 7^log₂n = n^log₂7
• 第二项的等比数列求和结果和n² * (7/4)^log₂n同阶，化简后也是n^log₂7
• 第三项的等比数列求和结果和7^log₂n同阶，即n^log₂7

所有项的最高阶均为n^log₂7，和主定理的推导结果一致。

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