# 第 22 章 复杂度分析与算法设计方法


> 本章回答一个决定生死的问题：**给我一个规模为 N 的输入，我该写什么样的算法？** 复杂度分析不是"写完代码再算一算"的收尾工作，而是**动手之前**的决策——它把"暴力能过"与"必须优化"分开，也把"优化到什么程度才够"变成可计算的数字。

## 学习目标

读完本章，你应当能够：

1. 用渐进记号（`O`、`Ω`、`Θ`）描述算法消耗，并区分最好、最坏、平均三种口径；
2. 依据输入规模与时限**反推可接受的复杂度上界**，据此排除不可行的做法；
3. 用摊还分析论证"单次偶尔很贵、整串操作的总代价被摊薄"这一情形；
4. 对 `T(n) = a·T(n/b) + f(n)` 型递归式用主定理（master theorem）判定量级；
5. 按"暴力 → 找重复计算 → 换载体 → 验口径"的路径完成优化，并说明每一步为什么成立；
6. 用常数因子校正理论复杂度，判断 `O(N log N)` 与 `O(N)` 在特定规模下谁更快。

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| 数组、哈希表、栈、队列的基本操作代价 | 22.1 节给出基本操作的约定；数据结构细节见第 23 章 |
| 循环嵌套与基本操作次数的估算 | 22.2.3 节从零演示计数过程 |
| 对数与指数运算法则（`log(ab) = log a + log b`） | 22.2.3 节推导增长阶时逐步用到 |
| 递归函数的执行过程 | 22.5.1 节用递归树重讲一遍 |
| Python 列表操作与运行时间测量的基本方法 | 第 26.5 节专门讲 Python 的性能陷阱 |

## 22.1 复杂度是什么：三种口径与两类资源

在真实机器上，运行时间取决于主频、缓存命中率、解释器版本——这些都与算法本身无关。于是我们改用一个**与机器无关**的量：**基本操作的执行次数随输入规模增长的趋势**。两个约定必须先固定：**基本操作**由分析者指定，通常取"比较""加法""赋值""数组访问"这类常数代价动作；**输入规模**由问题的自然参数决定——数组问题是元素个数 `N`，图问题是点数 `V` 与边数 `E`，矩阵问题是阶数 `m`、`k`、`n`。**基本操作**的选择影响常数因子，**不影响增长阶**，因此复杂度分析可以先粗后细：先用增长阶判断方案是否可行，再用常数因子判断同阶方案谁更快；把这两步颠倒，就会在错误的方案上做精细优化。

同一个算法在不同输入上的执行次数可以差很多。以顺序查找为例：目标是第一个元素时比较 1 次（最好情况），在末尾或不存在时比较 `N` 次（最坏情况），等概率分布下期望 `(N+1)/2` 次（平均情况）。

工程与考试默认使用**最坏情况**：它是**保证**，而平均情况依赖输入分布假设；对抗性测试数据往往不满足该假设；且最坏情况分析通常更简单。快速排序在"等概率随机排列"下平均 `O(N log N)`，但面对已排序输入且固定取首元素为基准时退化到 `O(N²)`——**看到 `O(N log N)` 时要先问一句：这是在什么分布下成立的？**

资源分两类：**时间复杂度**是基本操作次数随规模的增长，**空间复杂度**是额外占用的存储单元数随规模的增长（通常只计辅助空间，不含输入本身）。二者经常可以互换，这是 22.7 节"空间换时间"的来源。

## 22.2 渐进记号与常见增长阶

### 22.2.1 三个记号

```
O（大 O）：f(n) = O(g(n))      ⟺ 存在 c > 0 与 n₀，使一切 n ≥ n₀ 有 f(n) ≤ c·g(n)
Ω（大 Omega）：f(n) = Ω(g(n))  ⟺ 存在 c > 0 与 n₀，使一切 n ≥ n₀ 有 f(n) ≥ c·g(n)
Θ（大 Theta）：f(n) = Θ(g(n))  ⟺ f(n) = O(g(n)) 且 f(n) = Ω(g(n))
```

`O` 给上界（最多长这么快）、`Ω` 给下界（至少花这么多）、`Θ` 给紧确界（就是这么快）。三个定义都含常数 `c` 与阈值 `n₀`，这就是"渐进"的全部含义：**放弃有限范围内的具体倍数，只保留 n 足够大时的增长形状。**

```
例：f(n) = 3n² + 100n + 5000

取 c = 4、n₀ = 200：n ≥ 200 时 100n + 5000 ≤ n²，于是 f(n) ≤ 3n² + n² = 4n²  ⟹ f(n) = O(n²)
取 c = 3、n₀ = 1：f(n) ≥ 3n²                                              ⟹ f(n) = Ω(n²)
两者合起来：f(n) = Θ(n²)
```

> [!NOTE]
> 低阶项与系数在渐进意义下被吞掉，但**在真实运行时间中可能主导**。`n = 100` 时 `100n + 5000` 占了 `f(100)` 的近三分之一。这就是为什么给出量级之后还要补一句常数因子的讨论。

### 22.2.2 常见增长阶对照表

| 增长阶 | 名称 | `n = 100` | `n = 10⁵` | 典型算法 |
|---|---|---|---|---|
| `O(1)` | 常数 | 1 | 1 | 哈希表查找、数组按下标访问 |
| `O(log n)` | 对数 | ≈6.6 | ≈17 | 二分查找、堆的上浮下沉 |
| `O(n)` | 线性 | 100 | 10⁵ | 一次遍历、前缀和预处理 |
| `O(n log n)` | 线性对数 | ≈664 | ≈1.7×10⁶ | 归并排序、堆排序、一次全局排序 |
| `O(n²)` | 平方 | 10⁴ | 10¹⁰ | 两两枚举、朴素矩阵乘 |
| `O(n³)` | 立方 | 10⁶ | 10¹⁵ | Floyd、三重循环矩阵乘 |
| `O(2ⁿ)` | 指数 | ≈1.3×10³⁰ | 不可行 | 子集枚举、朴素子集和 |
| `O(n!)` | 阶乘 | ≈3.6×10⁶ | 不可行 | 不可行 | 全排列枚举、朴素 TSP |

两个必须记住的锚点，把抽象的对数变成可感的数字：

```
n = 10⁵ 时：log₂ n ≈ 17，n log₂ n ≈ 1.7 × 10⁶

"一次排序"相对"一次遍历"只贵 17 倍，
而"两两枚举"相对"一次遍历"贵 10⁵ 倍。
```

### 22.2.3 运算律与计数方法

| 规则 | 形式 | 例 |
|---|---|---|
| 加法取最大 | `O(f + g) = O(max(f, g))` | `O(n + n log n) = O(n log n)` |
| 常数可丢 | `O(c·f) = O(f)` | `O(3n) = O(n)` |
| 乘法保留 | `O(f·g) = O(f)·O(g)` | `O(n)·O(log n) = O(n log n)` |
| 对数底无关 | `log_a n = log_b n / log_b a`，换底只差常数 | `log₂ n` 与 `log₁₀ n` 同阶 |
| 嵌套循环相乘 | 外层 `n` 次、内层 `m` 次 ⟹ `O(n·m)` | 矩阵乘三重循环 `O(mkn)` |

有一条**极易出错**的例外：**只有内层循环次数与外层变量无关时**才能直接相乘。

```python
# 内层与外层无关 ⟹ 总次数 n²
total = 0
for i in range(n):
    for j in range(n):
        total += 1

# 内层次数依赖外层 ⟹ 总次数是等差数列求和 1+2+…+(n−1) = n(n−1)/2
# 量级仍是 n²，但常数是 1/2 —— 这类循环必须靠求和而不是相乘来数
total = 0
for i in range(n):
    for j in range(i):
        total += 1
```

## 22.3 从输入规模反推可接受复杂度

### 22.3.1 经验标尺的由来

机考与评测系统时限通常为 `1 ~ 2` 秒。Python 每秒大约完成 `10⁶ ~ 10⁷` 次"基本操作"（指循环体内的简单算术与赋值，不含函数调用与对象创建）。取保守值：

```
安全线：一次评测内基本操作总数 ≲ 10⁷      （Python，1 秒时限）
C/C++ 同类场景可比 Python 宽松 20 ~ 50 倍
```

把安全线除以各复杂度的单位代价，得到下表。

| 输入规模 `N` | 可接受的复杂度 | 大致操作数 | 对应做法 |
|---|---|---|---|
| `N ≤ 10` | `O(N!)`、`O(2^N)` | ≤ 3.6×10⁶ | 全排列、子集枚举、朴素搜索 |
| `N ≤ 100` | `O(N³)` | 10⁶ | Floyd、三重循环 DP |
| `N ≤ 500` | `O(N²)` | 2.5×10⁵ | 两两枚举、区间 DP |
| `N ≤ 2000` | `O(N²)` | 4×10⁶ | 两两枚举仍在安全线内（真题 08-05 编程题 1） |
| `N ≤ 5000` | `O(N²)` 勉强 / `O(N√N)` | 2.5×10⁷ 偏险 | 需常数很小或换更优做法 |
| `N ≤ 10⁵` | `O(N log N)` 或 `O(N)` | 1.7×10⁶ / 10⁵ | 一次排序、双指针、前缀和、单调队列 |
| `N ≤ 10⁶` | `O(N)` 且常数极小 | 10⁶ | 必须向量化或快速读入 |
| `N ≤ 10⁹` | `O(log N)`、`O(√N)` | ≈31 / ≈3.2×10⁴ | 二分、快速幂、试除法判素数 |

> [!TIP]
> 拿到题目先看约束，**不要留到写完代码之后**。约束直接决定算法档次：`N ≤ 2000` 就该放心写 `O(N²)`；`N ≤ 10⁵` 就必须放弃所有 `O(N²)` 的想法，转向"每个元素只被常数次访问"的结构。

### 22.3.2 用真实数据校准标尺

理论换算要落到本机才可靠。用 `time.perf_counter` 实测一段极简循环的耗时，得到本机的"每秒基本操作数"，再据此判断某个 `N` 下某量级是否可行。

```python
import time

def measure_ops_per_second(reps=2_000_000):
    """实测本机每秒能完成多少次"循环体内的基本操作"。
    校准必须在目标机器上做一次：不同评测机的速度差异可达一个数量级。"""
    total = 0
    start = time.perf_counter()
    for i in range(reps):
        total += i * 2                 # 一次乘法 + 一次加法，代表最廉价的循环体
    return reps / (time.perf_counter() - start)


def feasible(n, cost_per_n, limit=1.0, ops_per_sec=None):
    """cost_per_n 是一个单位 n 上的循环次数：
    O(n^2) 取 n，O(n log n) 取位数，O(n) 取 1。返回是否在时限内跑得完。"""
    ops = ops_per_sec or measure_ops_per_second()
    return (n * cost_per_n) / ops <= limit
```

实测时注意一个反直觉现象：**循环体越简单，每条"操作"的耗时越接近解释器开销下限**。上表的 `10⁷` 是针对"极简循环体"的估计；一旦循环体里出现函数调用、切片、`append`，实际吞吐会下降数倍。

> [!WARNING]
> 危险信号：`N ≤ 10⁵` 而你的做法是"枚举所有点对 / 所有子数组 / 对每个元素再扫一遍全部候选"。这三类都是 `O(N²)`，在 `10⁵` 时是 `10¹⁰` 量级，**无论怎么优化常数都救不回来**。此时唯一正确的动作是换算法。

## 22.4 摊还分析：偶尔很贵，但平均很便宜

有些数据结构的单次操作最坏代价很高，但这种操作**极少发生**，且频率与上次发生的间隔成反比。用最坏情况估计整体代价会严重高估。**摊还分析**（amortized analysis）把一序列操作的总代价平均到每次操作上，得到一个**保证**（不是概率意义上的平均）。

| 手法 | 思路 | 适用场景 |
|---|---|---|
| 聚合法（aggregate） | 直接算 `k` 次操作的总代价，再除以 `k` | 操作序列有明显整体结构 |
| 记账法（accounting） | 给便宜操作"多收费"，余额留给昂贵操作 | 能说清"存钱"的物理含义 |
| 势能法（potential） | 定义势函数 `Φ`，摊还代价 = 实际代价 + `ΔΦ` | 需要严格形式化论证时 |

### 22.4.1 动态数组扩容：聚合法

Python 的 `list`、C++ 的 `vector` 都支持 `append`：底层数组写满时开一块**两倍大小**的新数组，把旧元素整体搬过去。单次 `append` 最坏代价是 `O(n)`，但连续 `n` 次的总代价是：

```
容量序列 1, 2, 4, 8, …，总搬运次数 = 1 + 2 + 4 + … + n/2 < n
总实际代价 = n 次写入 + 少于 n 次的搬运 < 2n
摊还到单次 append：2n / n = O(1)
```

关键在于 `1 + 2 + 4 + … + 2^k = 2^{k+1} − 1 < 2n` 这个几何级数。**正因为容量"翻倍"而不是"加一"，级数才收敛到 `O(n)`**：若改成"每次 +1"，总搬运次数变成 `0 + 1 + … + (n−1) = n(n−1)/2 = Θ(n²)`，摊还到单次就是 `Θ(n)` 的灾难。**摊还 `O(1)` 不是数据结构的天赋，而是扩容策略设计出来的结果。**

### 22.4.2 单调栈：每个元素至多进出一次

单调栈求"每个元素右侧第一个更大元素"：遍历时维护一个下标栈，新元素入栈前把所有比它小的栈顶弹出，被弹出的下标就找到了答案。**摊还论证**：每个下标恰好被 `append` 一次，因此被 `pop` 也至多一次；外层循环 `n` 次、内层 `pop` 总次数不超过 `n`，总代价 `≤ 2n = O(n)`。

> [!IMPORTANT]
> 见到"内层 `while` 里做 `pop` / 删除"的嵌套循环时，**不要直接相乘估阶**，而要数"每个元素被插入和删除各几次"。若每个元素至多进出各一次，总代价就是 `O(n)`。这条判据同时适用于单调栈（第 23.5 节）、单调队列（第 23.5 节）、滑动窗口双指针（第 23.3 节）、并查集路径压缩（第 25.2 节）。

### 22.4.3 摊还 ≠ 平均

| 概念 | 含义 | 依赖输入分布 | 是否为保证 |
|---|---|---|---|
| 平均情况 | 对**输入分布**取期望 | 是 | 否 |
| 摊还 | 对**操作序列**取平均，最坏输入下也成立 | 否 | 是 |

"动态数组 `append` 摊还 `O(1)`"意味着**无论 append 什么内容**，`n` 次连续 append 的总耗时都是 `O(n)`。这是对任意输入序列的保证，因此可以安全写进性能承诺。

## 22.5 递归式的求解：主定理

### 22.5.1 递归树直觉

归并排序的递推式是 `T(n) = 2T(n/2) + O(n)`，展开成树：

```
                    n                     ← 代价 n
              ／          ＼
          n/2              n/2            ← 代价 n/2 + n/2 = n
        ／    ＼          ／    ＼
      n/4    n/4      n/4      n/4        ← 代价 4 × n/4 = n
       …      …        …        …
      1      1   …    1        1          ← 代价 n × 1 = n

每层代价都是 n，层数 = log₂ n  ⟹  T(n) = O(n log n)
```

递归树法的要点是**每层总代价 × 层数**：每层代价相同则答案是 `每层代价 × log n`；每层代价等比递减（如 `T(n) = T(n/2) + n`）则根节点主导，答案是 `O(n)`。

### 22.5.2 主定理的三种情形

对 `T(n) = a·T(n/b) + f(n)`（`a ≥ 1`、`b > 1`），令临界指数 `c* = log_b a`：

| 情形 | 条件 | 结论 | 直觉 |
|---|---|---|---|
| 1 | `f(n) = O(n^(c*−ε))`，`ε > 0` | `T(n) = Θ(n^c*)` | 叶子层主导，分解本身很便宜 |
| 2 | `f(n) = Θ(n^c* · log^k n)`，`k ≥ 0` | `T(n) = Θ(n^c* · log^(k+1) n)` | 每层代价相当，层数决定一切 |
| 3 | `f(n) = Ω(n^(c*+ε))` 且满足正则条件 | `T(n) = Θ(f(n))` | 根节点主导，合并开销盖过分治 |

记忆锚点：**先算 `log_b a`，再拿 `f(n)` 与 `n^log_b a` 比大小**；比出"小、相等、大"，分别落在三种情形。

| 递归式 | `a` | `b` | `log_b a` | `f(n)` | 情形 | 结果 |
|---|---|---|---|---|---|---|
| `T(n) = 2T(n/2) + n` | 2 | 2 | 1 | `n` | 2（k=0） | `Θ(n log n)` 归并排序 |
| `T(n) = T(n/2) + 1` | 1 | 2 | 0 | `1` | 2（k=0） | `Θ(log n)` 二分查找 |
| `T(n) = 2T(n/2) + 1` | 2 | 2 | 1 | `1` | 1 | `Θ(n)` 二叉树遍历 |
| `T(n) = 7T(n/2) + n²` | 7 | 2 | ≈2.81 | `n²` | 1 | `Θ(n^2.81)` Strassen 矩阵乘 |

> [!WARNING]
> 主定理**只覆盖三类情形**。`T(n) = 2T(n/2) + n log n` 落在情形 2 与 3 之间（`f(n)` 比 `n^c*` 大但只大一个对数因子），标准形式给不出结论，需用扩展形式或直接画递归树。另外 `T(n) = T(n−1) + n` 这种**减治型**不满足 `n/b` 形式，不能套主定理，直接展开求和得 `Θ(n²)`。

## 22.6 从暴力到优化：一条可复用的思维路径

优化的本质是**消除重复计算**。四步路径，每一步对应一类可识别的浪费：

```
① 写暴力，明确它的复杂度与瓶颈在哪一重循环
② 找出"被反复重算的量" —— 它们是优化的入口
③ 为这些量选载体：前缀和 / 单调结构 / 哈希表 / 排序 / DP 状态
④ 验证新做法仍正确（尤其"边界口径"没变），再用 22.3 的标尺确认够快
```

### 22.6.1 同一量反复重算 → 排序一次

【2026-09-09 编程题 1】的朴素做法是每轮扫全表挑出分数最高的候选，重复 `remaining` 轮，工作量 `O(remaining · L·H·N)`，两个因子都可能到 `10⁴`，乘起来 `10⁹` 量级必然超时。

关键在于识别重复：**这 `remaining` 轮在做的事，是按同一个序反复取前几名**，而"同一个序的前几名"一次排序就能确定。复杂度从 `O(M·n)`（`n = L·H·N` 为候选总数、`M` 为名额数）降到 `O(n log n)`。

多级优先级也在这里完成：把"分数降序、层升序、头升序、token 升序"编码成元组键 `(−score, l, h, t)`。**负号的作用是把"降序"统一成"升序"，让所有维度都能用同一个 `sort()` 解决**（第 23.6 节展开）。

### 22.6.2 暴力可过就别优化

【2026-08-05 编程题 1】的约束是 `N ≤ 2000`，`O(N²)` 在本例中是 `2×10⁶` 次距离计算，**远在安全线内**。正确的决策是直接写两两枚举，把省下的时间花在核对规则口径上。这道题真正的分差点是三条纪律：邻域判定**包含自身**（计数器初值取 `1`）；**必须先把全部核心点确定下来**再标注边界点；曼哈顿距离对称，只枚举 `j > i` 的一半点对。

> [!NOTE]
> 12 道编程题里有 4 道属于"题面把公式和流程写全、照着实现"的类型。在这类题上追求优化是**负收益**：省下的运行时间远小于理解错规则带来的风险。**先判断题目要的是"算法"还是"纪律"。**

### 22.6.3 消掉一重枚举

【2026-08-05 编程题 2】的状态需要记 `(进度, 上一个 Agent)`，转移时枚举两者，得 `O(100·N²)`；`N = 10⁵` 时是 `10¹²` 量级。

突破口不是换数据结构，而是**发现那重枚举只求一个最小值**。把每层的"最小值及其持有者"和"排除该持有者后的次小值"预先维护好，转移时按 `k` 是否等于持有者二选一，就把 `O(100·N²)`（`N = 10⁵` 时约 `10¹²`）压到 `O(100·N)`（约 `10⁷`，恰好落在 Python 安全线附近）。完整的正确性论证（"排除任一元素后的最小值只能是最小值或次小值"）与四条更新规则见第 24.4.3 节。

### 22.6.4 窗口统计量从 `O(N·w)` 到 `O(N)`

【2026-09-04 编程题 1】需要对每个点算"以它为中心的窗口"的均值与标准差。逐点重扫是 `O(N·w)`，`w` 可到 `N−1`，最坏近 `10⁸` 次加法。

重复的量是**窗口内的和**：相邻两个窗口的和高度重叠。前缀和把"区间和"变成两次查询之差的 `O(1)` 操作，总代价降到 `O(N)`。完整推导与代码见第 23.4 节。

## 22.7 空间换时间与常数因子

### 22.7.1 空间换时间的四种形态

| 形态 | 做法 | 时间收益 | 空间代价 | 本书实例 |
|---|---|---|---|---|
| 预计算 | 事先算好所有查询的答案 | `O(1)` 查询 | `O(状态数)` | 前缀和、距离矩阵 |
| 缓存 | 记住已算过的中间结果 | 消掉递归重复 | `O(状态数)` | 记忆化搜索、DP 表 |
| 冗余信息 | 额外存"次优信息" | 消掉一重枚举 | 常数倍 | 最小/次小值（第 24.4.3 节） |

> [!IMPORTANT]
> 空间换时间有一个**前提**：被换掉的时间必须是**重复计算**。若一个量只被用一次，缓存它只是纯浪费内存。判断方法很直接——问一句"这个值会被查询几次"，超过一次才值得存。

### 22.7.2 常数因子：什么时候 `O(N)` 输给 `O(N log N)`

理论量级只给趋势，真实运行时间大致是 `(基本操作次数) × (单次操作的常数代价)`。Python 中不同写法的常数代价可差 50 倍以上：

| 写法 | 相对代价 | 说明 |
|---|---|---|
| 局部变量算术 | 1 | 最快，直接走解释器快路径 |
| 列表推导 | 约 1 | 循环在 C 层完成，比显式 `for` + `append` 快 2~3 倍 |
| 内置函数 `sum`、`max`、`sorted` | 约 1/10 | 完全在 C 层执行 |
| 纯 Python 的 `for` 循环体 | 约 3~5 | 每轮都有解释器开销 |
| 每轮调用一次自定义函数 | 约 20~50 | 函数调用与帧创建是主要成本 |
| Numpy 向量化 | 约 1/100 | 但小数组时启动开销占主导 |

结论：**当两个方案的量级只差一个对数因子时，常数因子可以反超**。`N = 10⁵` 时 `n log n ≈ 1.7×10⁶`，而"常数大 20 倍的 `O(n)` 做法"等价于 `2×10⁶`——两者实际打平。这正是【2026-09-02 编程题 1】里"只对窗口内打分虽把 `O(N²)` 降到 `O(Nω)`，却因为丢掉向量化反而更慢"的根因。

```python
def loop_sum(n):
    s = 0
    for i in range(n):                 # 每轮都有解释器开销
        s += i
    return s


def builtin_sum(n):
    return sum(range(n))               # 循环全在 C 层，量级相同但常数小一个数量级
```

**两者都是 `O(n)`，但实测相差数倍**：量级分析给的是"及格线"，常数因子决定"实际分数"。

## 22.8 复杂度分析的完整工作流
```
① 读约束，定位规模 N 与其他维度（如 A、B、C、L、H）
② 用 22.3 节标尺把 N 映射到"可接受复杂度档次"
③ 设计算法，写出它的复杂度表达式（含常数项的顺序）
④ 与 ② 得到的档次对比：达标 → 检查边界口径、直接编码；
                        超标 → 回到 22.6 节的四步路径找重复计算
⑤ 编码后用 22.3.2 的实测脚本在目标机器上抽查最坏数据
⑥ 写出"为什么这个上界成立"的一句话说明
```

第 ⑥ 步常被忽略，但它在两处有硬价值：**笔试与面试的说明题会直接要求；而当你写不出那句话时，说明你并不真的理解自己的算法**。

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 渐进记号 | `O` 上界、`Ω` 下界、`Θ` 紧确界，定义含常数 `c` 与阈值 `n₀` | 把 `O` 当"等于"，写出 `O(n) = O(n²)` |
| 默认口径 | 工程与考试默认使用**最坏情况** | 用"平均 `O(N log N)`"为快排退化输入开脱 |
| 规模反推 | `N ≤ 2000` 可用 `O(N²)`；`N ≤ 10⁵` 必须 `O(N log N)` 或 `O(N)` | 在 `10⁵` 上写两两枚举，指望常数优化救回来 |
| Python 安全线 | 约 `10⁶ ~ 10⁷` 次基本操作/秒，循环体复杂时显著下降 | 用 C++ 的经验阈值（`10⁸`）估算 Python 的预算 |
| 摊还分析 | 数"每个元素进出几次"，而非把嵌套层数相乘 | 看到内层 `while` 就判 `O(n²)`，误杀单调栈与并查集 |
| 摊还 ≠ 平均 | 摊还是对操作序列的**最坏情形保证**，平均依赖分布 | 把二者混为一谈，导致性能承诺失效 |
| 主定理 | 先算 `log_b a`，再与 `f(n)` 比大小；只覆盖三种情形 | 对 `T(n) = T(n−1) + n` 硬套主定理 |
| 优化路径 | 暴力 → 找重复计算 → 换载体 → 验口径 | 一上来就追求最优做法，忽略题目可能只考规则纪律 |
| 空间换时间 | 只有被缓存的量会被查询多次时才划算 | 缓存只用一次的中间结果，白白吃内存 |
| 常数因子 | 量级只差一个对数因子时，常数可以反超 | 为省一个 `log` 丢掉向量化，实际变慢 |

## 自测题

**Q1**（计算）某算法执行 `f(n) = 5n³ + 200n² + 10⁶` 次基本操作。求它的 `Θ` 记号，并说明 `n` 取多大时三次项开始主导。

<details><summary>答案与解析</summary>

`f(n) = Θ(n³)`。

取 `c₁ = 5`、`n₀ = 1` 得 `f(n) ≥ 5n³`，故 `f(n) = Ω(n³)`；取 `c₂ = 6`，只要 `200n² + 10⁶ ≤ n³`（约 `n ≥ 260`）即得 `f(n) ≤ 6n³`，故 `f(n) = O(n³)`。

**常见错误**：把常数 `10⁶` 当成最高次项的一部分。常数项在渐进意义下必被吞掉，但它在 `n = 100` 时贡献了 `f(100)` 的绝大部分——这正是"渐进量级不反映小规模真实速度"的典型例子。

</details>

**Q2**（推导）用聚合法证明：若动态数组扩容策略是"每次容量加 1"，则 `n` 次 `append` 的摊还代价是 `Θ(n)`，而不是 `O(1)`。

<details><summary>答案与解析</summary>

设初始容量为 1。第 `i` 次 `append`（`i ≥ 2`）触发扩容时需新建容量为 `i` 的数组并搬运 `i − 1` 个元素。

```
总搬运次数 = 0 + 1 + 2 + … + (n−1) = n(n−1)/2
总代价（写入 + 搬运）= n + n(n−1)/2 = Θ(n²)
摊还到单次 append = Θ(n²)/n = Θ(n)
```

对照翻倍策略：容量序列 `1, 2, 4, …`，搬运总次数是几何级数 `< n`，总代价 `Θ(n)`，摊还 `O(1)`。

**易错点**：只算搬运而忘记每次 `append` 本身的写入。写入的 `n` 次在两种策略下相同，不影响对比结论，但完整推导应保留。

</details>

**Q3**（判断）有人说："单调栈的代码有两层嵌套循环，所以它是 `O(n²)`。" 判断正误并给出理由。

<details><summary>答案与解析</summary>

错误，单调栈是 `O(n)`。

内层 `while` 每执行一次就 `pop` 一个下标，而**每个下标整个过程只被 `push` 一次**，因此至多被 `pop` 一次。外层 `n` 次、内层 `pop` 总次数 `≤ n`，总操作数 `≤ 2n`。

**这是本章最值得带走的一条判据**：看到嵌套循环时先问"内层操作会不会重复处理同一个元素"，而不是机械相乘。同类结构还有双指针滑动窗口（左右指针各单调移动）、并查集路径压缩（`find` 摊还 `O(α(n))`）。

</details>

**Q4**（计算）某题约束为 `N ≤ 10⁵`、时限 1 秒、评测语言 Python。判断三种做法是否可行：

```
(a) 对每个元素再向后扫描全部其他元素求最大值
(b) 先把数组排序，再线性扫描一遍
(c) 用单调队列一次扫过数组求所有长度为 k 的窗口最大值
```

<details><summary>答案与解析</summary>

(a) **不可行**。`O(N²)` 在 `N = 10⁵` 时约 `5×10⁹` 次内层操作，远超 Python 约 `10⁷` 的安全线，差两个数量级以上。

(b) **可行**。`O(N log N)` 约 `1.7×10⁶` 次比较，加一次线性扫描 `10⁵`；且 `sorted` 在 C 层执行，常数更小。

(c) **可行且最优**。`O(N)`，`10⁵` 次操作，且不需要排序的 `log` 因子。

**延伸**：若只需要"全局最大值"这一个答案，(c) 也退化为一次线性扫描，连单调队列都不需要。**优化到什么程度取决于题目需要回答多少种查询**——这是"按需优化"的核心。

</details>

**Q5**（推导）用主定理求解 `T(n) = 4T(n/2) + n`，并说明结果的直觉含义。

<details><summary>答案与解析</summary>

`a = 4`、`b = 2`，临界指数 `c* = log₂ 4 = 2`。`f(n) = n = O(n^(2−ε))`（取 `ε = 1`），满足**情形 1**，故 `T(n) = Θ(n²)`。

直觉：递归分出的 4 个子问题合起来贡献 `4T(n/2)`，叶子数量随层数按 `4^层数` 增长，而每层节点的工作量按 `2^层数` 下降。叶子层的总量 `4^(log₂ n) = n²` 压倒性地大于根节点的工作量 `n`，所以总代价由叶子决定。

**易错点**：把 `4T(n/2)` 里的 `4` 当成可忽略的常数。`a` 的大小直接决定 `log_b a`，从而决定三种情形的归属。

</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【2026-08-05 编程题 1】基站空间重叠区域识别 | `N ≤ 2000` 时 `O(N²)` 两两枚举完全可行，不必优化 | 22.3.1、22.6.2 |
| 【2026-08-05 编程题 2】多 Agent 协作任务调度 | 朴素 `O(100N²)` 超时；最小/次小值消掉一重枚举得 `O(100N)` | 22.3.1、22.6.3 |
| 【2026-08-26 编程题 1】运维任务收益最大化 | 状态规模由 `A×B` 决定，`O(nAB)` 是唯一瓶颈 | 22.3.1、22.2.3 |
| 【2026-08-26 编程题 2】多头注意力双向整数 RNN | 各维度 ≤ 5、`N ≤ 10`，总运算量不足 `10⁵`，照公式直写 | 22.3.1、22.6.2 |
| 【2026-09-02 编程题 1】滑动窗口注意力 | 把 `O(N²d)` 降到 `O(Nωd)` 会丢掉向量化，常数反超 | 22.7.2 |
| 【2026-09-02 编程题 2】全整型量化矩阵乘 | `O(mkn)`，`m=k=n=100` 时约 `10⁶` 次点积 | 22.3.1 |
| 【2026-09-04 编程题 1】时间序列清洗与特征评分 | 前缀和把窗口统计从 `O(Nw)` 压到 `O(N)` | 22.6.4、22.7.1 |
| 【2026-09-04 编程题 2】模型训练资源分配 | `O(nC)` 转移，`C ≤ 1000`、`n ≤ 100` 时约 `10⁵` | 22.3.1 |
| 【2026-09-09 编程题 1】动态 KV 缓存稀疏优化 | 反复取前 k 名的 `O(M·n)` 被一次排序 `O(n log n)` 取代 | 22.6.1 |
| 【2026-09-09 编程题 2】CDN 分发服务器选址 | `O(T·p²)` 迭代聚类，`p < 100`、`T` 为个位数 | 22.2.3、22.3.1 |
| 【2026-09-11 编程题 1】端侧大模型动态权重剪枝 | `N ≤ 10⁵` 时 `O(N²)` 是 `5×10⁹` 次，必须双指针 + 单调队列 | 22.3.1、22.4.2 |
| 【2026-09-11 编程题 2】文档片段相关性判定 | `O(N²)` 建邻域 + 并查集摊还 `O(α(n))` | 22.4.2、22.5.2 |

## 延伸阅读

- Cormen, Leiserson, Rivest, Stein，《Introduction to Algorithms》（CLRS）第 3 章"函数的增长"、第 4 章"分治策略"、第 17 章"摊还分析"——主定理与摊还三种手法的标准来源。
- Sedgewick & Wayne，《Algorithms》第 1.4 节"算法分析"——"从输入规模反推可接受复杂度"这一实践视角讲得最清楚。
- Tarjan, "Amortized Computational Complexity"（SIAM J. Algebraic Discrete Methods, 1985）——摊还分析的经典综述，势能法的原始出处。
- Python 官方文档 `timeit` 与 `collections` 模块说明——建立本机常数因子直觉的第一手材料。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch22/  

