AG1 时间复杂度

1. 概述

通过对题目给的数据规模做时间复杂度估计，可以帮助我们判断选取哪种算法。

所以学会估计某算法的时间复杂度非常重要。

一般来说，不希望复杂度的规模到达 $10^{10}$ 量级，否则会爆TLE。

算法的时间复杂度通常用大 $O$ 表示法（渐进上界）表示：

我们试图找到 $g(n)$ ，这样可以用 $g(n)$ 来对算法的计算次数 $f(n)$ 做一个估计。因为当数据 $n$ 足够大时，两者仅仅相差一个常系数 $c$ 。

大 $O$ 表示法既可以表示一般时间复杂度，也可以表示最坏时间复杂度，视语境而定。
但是严格意义上，$Θ$ 应表示平均时间复杂度，$Ω$ 应表示最佳时间复杂度。

2. 常见的时间复杂度

见 https://www.bigocheatsheet.com/ ，如下图：

3. 时间复杂度的估计

基本方法是

1. 求运算次数 $T(n)$ ；
2. 取 $T(n)$ 的最高阶项。

3.1 迭代情形

这类算法不包含函数自身调用。主要用循环、顺序和条件分支构成。

3.1.1 单层循环

模式一：常数循环

for (int i = 1; i <= 10; i++) {   // 10次，固定
    cout << i << endl;             // O(1) 操作
}

• 循环次数与输入规模 $n$ 无关
• 时间复杂度 = $O(1)$

模式二：线性

// 常数步长递增
for (int i = 1; i <= n; i++) {       // n次
    cout << i << endl;
}

// 常数步长递减
for (int i = n; i >= 1; i--) {       // n次
    cout << i << endl;
}

// 常数 c 步长：n/c 次，还是 O(n)
for (int i = 1; i <= n; i += 5) {    // n/5次
    cout << i << endl;
}

• 循环变量每次增加/减少一个常数
• 时间复杂度 = $O(n)$

模式三：双指针

// 左右双指针
int l = 0, r = n - 1;
while (l <= r) {
    if (condition) {
        l++;
    } else {
        r--;
    }
}

• l 和 r 从两端向中间移动，相遇时结束
• 时间复杂度 = $O(n)$

模式四：指数

// 指数增长
int i = 1;
while (i < n) {
    cout << i << endl;    // O(1)
    i *= 2;               // 每次翻倍
}

// 指数衰减
int i = n;
while (i > 0) {
    cout << i << endl;
    i /= 2;               // 每次减半
}

• 循环终止条件：$2^k ≥ n → k = log_2(n)$
• 时间复杂度 = $O(\text{log }n)$

模式五：双指数

int i = 2;
while (i <= n) {
    cout << i << endl;
    i = pow(i, c);         // i 的 c 次方（c > 1）
}

• 终止条件：$2^{c^k} = n → c^k = log n → k = log_c(log n)$
• 时间复杂度 = $O(\text{log log }n)$

3.1.2 嵌套循环

模式一：独立循环

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << ", " << j << endl;  // O(1)
    }
}

• 计算：外层 $n$ 次 × 内层 $n$ 次 = $n^2$ 次 → $O(n^2)$
• 可抽象为矩形

模式二：受控循环

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        cout << i << ", " << j << endl;
    }
}

// 或
for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
        cout << i << ", " << j << endl;
    }
}

• 计算：
  • i = 0 时，内层执行 0 次
  • i = 1 时，内层执行 1 次
  • i = n-1 时，内层执行 n-1 次
  • 总次数 = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2
• 时间复杂度 = $O(n^2)$
• 可抽象为三角形

模式三：混合

for (int i = 0; i < n; i++) {       // O(n)
    int j = 1;
    while (j < n) {
        cout << i << ", " << j << endl;
        j *= 2;                     // O(log n)
    }
}

• 计算：外层 $O(n)$ × 内层 $O(\text{log }n)$ = $O(n\text{ log }n)$

注意

若循环中存在条件判断，一般直接考虑最坏情况就行 。

3.2 递归情形

递归算法通过函数调用自身来解决问题，包含两个关键要素：

1. 终止条件：不再递归，直接返回结果；
2. 递推关系：将原问题分解为子问题，并描述子问题与原问题的关系。

如何理解递推关系式

$T(n) = (子问题个数) × T(子问题规模) + (合并子问题的时间)$

3.2.1 递归树法

思想：用树形结构可视化递归调用的展开过程。

• 每个节点表示一次递归调用的代价（不包含子递归）
• 树的深度表示递归的层数
• 每层总代价 = 该层所有节点的代价之和
• 总复杂度 = 所有层代价之和

关于代价，有如下三种情况：

1. 代价递减

考虑递推关系式 $$T(n) = 2T(\frac{n}{2}) + n^2$$
以下的递归树图展示了每次调用时产生的代价：

如图，可以见到，每层代价构成一个等比数列，可以计算总代价：

$$总代价 = n^2 × (1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + ...) = n^2 × 2 = O(n²)$$

这种情况下的树高并不重要。

可以见到此时的时间复杂度主要受根节点代价控制。

2. 代价不变

考虑递推关系式（例如归并排序） $$T(n) = 2T(\frac{n}{2}) + n$$

以下的递归树图展示了每次调用时产生的代价：

如图，可以见到，每层代价均为 $n$ ，且所有分支深度相同，考虑树高：

$$总代价 = O(n\text{log }n)$$

3. 代价递增

考虑递推关系式 （例如遍历二叉树）$$T(n) = 2T(\frac{n}{2}) + 1$$
以下的递归树图展示了每次调用时产生的代价：

如图，可以见到，每层代价按照2的幂次逐渐增长，可以计算总代价：

$$总代价 = 1 + 2 + 4 + \dots + 2^{log_2 n} = 2n - 1 = O(n)$$

可以见到，此时的时间复杂度主要跟叶子节点层的代价相关。

上述情形的递归树都是平衡的，若递归表达式中，可以看出所有子问题不是等大的，那么画出的递归树就不是平衡的。

对于非等大子问题，见下例：

$$T(n) = T(\frac{n}{3})+ T(\frac{2n}{3}) + n$$

它的递归树如下图所示：

注意这里的树不是平衡的，左边路径最短，右边路径最长。我们考虑最坏的情况，那么最长路径的长度为 $log_{\frac{3}{2}} n$，所以这里的时间复杂度估计为 $O(n\text{ log }n)$。

3.2.2 Master Theorem 公式

适用形式如下：

$$T(n) = aT(\frac{n}{b}) + f(n)$$

其中：

• $a ≥ 1$：子问题的个数
• $b > 1$：每个子问题的规模是原问题的 1/b
• $f(n)$：分解和合并的代价

定义临界指数 $c^* = log_b(a)$，考虑 $f(n)$ 与多项式 $n^{c^*}$ 之间的关系:

1. $f(n)$ 多项式地小于 $n^{c^*}$ ：$T(n) = Θ(n^{c^*})$
2. $f(n)$ 和 $n^{c^*}$ 同阶：$T(n) = Θ(n^{log_b a}·log n)$
3. $f(n)$ 多项式地大于 $n^{c^*}$：$T(n) = Θ(f(n))$

可以结合递归树理解。