第 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 复杂度是什么：三种口径与两类资源

在真实机器上，运行时间取决于主频、缓存命中率、解释器版本——这些都与算法本身无关。于是我们改用一个与机器无关的量：基本操作的执行次数随输入规模增长的趋势。两个约定必须先固定：基本操作由分析者指定，通常取"比较"“加法"“赋值"“数组访问"这类常数代价动作；输入规模由问题的自然参数决定——数组问题是元素个数 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 三个记号

1
2
3

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 足够大时的增长形状。

1
2
3
4
5

例：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²)

22.2.2 常见增长阶对照表

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

1
2
3
4

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

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

22.2.3 运算律与计数方法

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 内层与外层无关 ⟹ 总次数 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⁷ 次"基本操作”（指循环体内的简单算术与赋值，不含函数调用与对象创建）。取保守值：

1
2

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

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

22.3.2 用真实数据校准标尺

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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，实际吞吐会下降数倍。

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

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

22.4.1 动态数组扩容：聚合法

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

1
2
3

容量序列 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)。

22.4.3 摊还 ≠ 平均

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

22.5 递归式的求解：主定理

22.5.1 递归树直觉

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

1
2
3
4
5
6
7
8
9

                    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：

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

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

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

1
2
3
4

① 写暴力，明确它的复杂度与瓶颈在哪一重循环
② 找出"被反复重算的量" —— 它们是优化的入口
③ 为这些量选载体：前缀和 / 单调结构 / 哈希表 / 排序 / 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 的一半点对。

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 空间换时间的四种形态

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

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

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

1
2
3
4
5
6
7
8
9

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 复杂度分析的完整工作流

1
2
3
4
5
6
7

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

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

本章小结

自测题

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

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

1
2
3

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

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

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

1
2
3

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

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

与真题的关联

延伸阅读

• 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 模块说明——建立本机常数因子直觉的第一手材料。