【软考 8T(n / 2)+n^2的时间复杂度如何计算？】

要计算递归式 ( T(n) = 8T(n/2) + n^2 ) 的时间复杂度，可以使用 主定理（Master Theorem） 或 递归树法。以下是详细步骤和结论：

一、主定理分析

主定理适用于形如 ( T(n) = aT(n/b) + f(n) ) 的递推式，其中 ( a \geq 1 ), ( b > 1 )。 代入本题参数：

• ( a = 8 ), ( b = 2 ), ( f(n) = n^2 )

1. 计算 ( \log_b a )： [ \log_2 8 = 3 \quad \Rightarrow \quad n^{\log_b a} = n^3 ]
2. 比较 ( f(n) ) 与 ( n^{\log_b a} )： [ f(n) = n^2 \quad \text{和} \quad n^{\log_b a} = n^3 ] 由于 ( n^2 = O(n^{3 - \epsilon}) )（取 ( \epsilon = 1 )），符合主定理 第一种情况。
3. 结论： [ T(n) = \Theta(n^{\log_b a}) = \Theta(n^3) ]

二、递归树法验证

1. 递归展开： 每层递归的总工作量为：
   • 第 ( k ) 层：( 8^k \cdot \left( \frac{n}{2^k} \right)^2 = 8^k \cdot \frac{n2}{4k} = 2^k n^2 )
2. 总工作量求和： 递归深度为 ( \log_2 n )，总工作量为： [ \sum_{k=0}^{\log_2 n - 1} 2^k n^2 = n^2 \cdot \sum_{k=0}^{\log_2 n - 1} 2^k = n^2 \cdot (2^{\log_2 n} - 1) = n^3 - n^2 ]
3. 叶子节点工作量： 叶子节点数为 ( 8^{\log_2 n} = n^{\log_2 8} = n^3 )，每个叶子节点的工作量为常数 ( \Theta(1) )，总工作量 ( \Theta(n^3) )。
4. 合并结果： 总时间复杂度为： [ T(n) = \Theta(n^3) + \Theta(n^3) = \Theta(n^3) ]

三、递推式展开验证

展开递推式至第 ( k ) 层： [ T(n) = 8^k T\left( \frac{n}{2^k} \right) + n^2 \sum_{i=0}^{k-1} 2^i ] 当 ( \frac{n}{2^k} = 1 )（即 ( k = \log_2 n )）时： [ T(n) = 8^{\log_2 n} T(1) + n^2 (2^{\log_2 n} - 1) = \Theta(n^3) + \Theta(n^3) = \Theta(n^3) ]

四、结论

通过主定理、递归树法和递推展开法，一致得出： [ T(n) = 8T(n/2) + n^2 \quad \text{的时间复杂度为} \quad \boxed{\Theta(n^3)} ] 这表明算法的执行时间随输入规模 ( n ) 以三次方的速度增长。