时间复杂度的计算问题
一、递归类时间复杂度的计算
(FDS HW1) 例题：递归关系如下，求时间复杂度。
\[
T(1) = 1
\]
\[
T(N) = 3T\left(\frac{N}{3}\right) + 1
\]
法一：主定理
递归关系 \( T(N) = aT\left(\frac{N}{b}\right) + O(N^d) \) 可以按照以下规则来解决：
- 如果 \( a > b^d \)，时间复杂度是 \( O(N^{\log_b a}) \)。
- 如果 \( a = b^d \)，时间复杂度是 \( O(N^d \log N) \)。
- 如果 \( a < b^d \)，时间复杂度是 \( O(N^d) \)。
根据该定理可以得到时间复杂度是 \(O(N)\)。
法二：递归树法
展开递归
- 第 1 层：一个问题大小为 \(N\)，工作量是 \(1\)。
- 第 2 层：3 个子问题，每个大小为 \(N/3\)，工作量是 \(3\)。
- 第 3 层：9 个子问题，每个大小为 \(N/9\)，工作量是 \(9\)。
- ...
- 第 \(k\) 层：\(3^k\) 个子问题，每个大小为 \(N/3^k\)，工作量是 \(3^k\)。
求高度
树的高度为 \(k\)，当子问题大小为 1 时，满足 \(\frac{N}{3^k} = 1\)，解得 \(k = \log_3 N\)。
总工作量
所有层的工作量之和为：
\[
T(N) = 1 + 3 + 9 + \dots + 3^{\log_3 N}
\]
这是一个等比数列，求和得到：
\[
T(N) = \frac{N - 1}{2}
\]
因此，时间复杂度是 \(O(N)\)。
二、迭代类时间复杂度的计算
Example
(FDS HW1) 例题：对于以下代码，最低上界时间复杂度是 \(O(N^3)\)。
if ( A > B ){
for ( i = 0; i < N*2; i ++ )
for ( j = N*N; j > i; j -- )
C += A;
}
else {
for ( i = 0; i < N*N/100; i ++ )
for ( j = N; j > i; j -- )
for ( k = 0; k < N*3; k ++)
C += B;
}
分析方法：逐层分析即可。
A > B 分支
总操作次数：
\[
\sum_{i=0}^{2N-1} (N^2 - i) = \underbrace{2N \cdot N^2}_{\text{外层总次数}} - \underbrace{\sum_{i=0}^{2N-1} i}_{\text{等差求和}} = 2N^3 - \frac{(2N-1) \cdot 2N}{2} = O(N^3)
\]
A ≤ B 分支
总操作次数：
\[
\sum_{i=0}^{N-1} \underbrace{(N - i)}_{\text{中间循环}} \cdot \underbrace{3N}_{\text{内层循环}} = 3N \cdot \sum_{i=0}^{N-1} (N - i) = 3N \cdot \frac{N(N+1)}{2} = O(N^3)
\]