【软考 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{n^2}{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 ) 以三次方的速度增长。