第 2 讲：渐近分析——O、Ω、Θ 与增长率

一、为什么要丢掉常数

先看一组真实数字。假设一台机器每秒执行 10⁹ 次基本操作：

n	n log n	n²	2ⁿ
10	33 ns	100 ns	1 μs
1 000	10 μs	1 ms	远超宇宙年龄
10⁶	20 ms	17 分钟	—
10⁹	30 s	31 年	—

n = 10⁶ 时，n log n 与 n² 差了约 5 万倍。没有任何常数因子、编译器优化或换语言能弥补这个差距。 把 Python 换成 C 大约快 50 倍——买不到这 5 万倍。

这就是渐近分析的全部动机：在足够大的输入上，增长率支配一切，常数因子无关紧要。 于是我们设计一套记号，故意把常数和低阶项扔掉。

⚠️ 但请记住前提是"足够大的输入"。如果 n 永远不超过 20，渐近分析可能给出错误的工程建议——这也是标准库排序在小数组上切回插入排序的原因（第 11 讲）。

二、三个记号的精确定义

设 f(n)、g(n) 是定义在自然数上的非负函数。

O：渐近上界

f(n) = O(g(n))  ⟺  ∃ c > 0, n₀ > 0, 使得对所有 n ≥ n₀：
                     0 ≤ f(n) ≤ c · g(n)

读作"f 至多以 g 的速度增长"。注意两个量词：常数 c 是存在，n 是对所有足够大的。

Ω：渐近下界

f(n) = Ω(g(n))  ⟺  ∃ c > 0, n₀ > 0, 使得对所有 n ≥ n₀：
                     0 ≤ c · g(n) ≤ f(n)

Θ：渐近紧确界

f(n) = Θ(g(n))  ⟺  f(n) = O(g(n)) 且 f(n) = Ω(g(n))
                ⟺  ∃ c₁, c₂ > 0, n₀：n ≥ n₀ 时 c₁g(n) ≤ f(n) ≤ c₂g(n)

      Θ(g)：夹住            O(g)：压住          Ω(g)：托住
   │      c₂·g(n)        │   c·g(n)         │    f(n)
   │     ╱               │  ╱               │   ╱
   │    ╱ f(n)           │ ╱  f(n)          │  ╱ c·g(n)
   │   ╱  ╱              │╱  ╱              │ ╱  ╱
   │  ╱  ╱ c₁·g(n)       │  ╱               │╱  ╱
   └────┼──────► n       └──┼──────► n      └──┼──────► n
        n₀                  n₀                 n₀

严格记号 o 与 ω

f(n) = o(g(n))  ⟺  ∀ c > 0, ∃ n₀：n ≥ n₀ 时 f(n) < c·g(n)   （lim f/g = 0）
f(n) = ω(g(n))  ⟺  lim f/g = ∞

类比（不严谨但好记）：

记号	O	Ω	Θ	o	ω
类比	≤	≥	=	<	>

⚠️ 类比在一处失效：实数上任意两数可比，函数不一定。n^(1+sin n) 与 n 之间三种关系都不成立。

三、四个必须避免的误用

误用 1：把 O 当成"就是这么快"

O 是上界，可以任意松。“插入排序是 O(n¹⁰⁰)“在数学上完全正确。

知道紧确界时就说 Θ。说 O 只是不肯把话说满。

工程语境里用 O 表达 Θ 的意思是可接受的约定，但读论文和写证明时必须分清。尤其是下界结论：第 12 讲的"比较排序需要 Ω(n log n)"，说成 O(n log n) 意思完全相反。

误用 2：把「最坏情况」当成「上界」

这是两个正交的维度：

	上界 O	下界 Ω
最坏情况	插入排序最坏是 O(n²)	插入排序最坏是 Ω(n²)（逆序输入）
最好情况	插入排序最好是 O(n)（已有序）	插入排序最好是 Ω(n)

所以"插入排序最好情况 Θ(n)、最坏情况 Θ(n²)“完全合法。O 回答"多快之内”，最坏情况回答"对哪个输入”。

误用 3：等号是滥用记号

f(n) = O(g(n)) 真正的意思是 f ∈ O(g)（O(g) 是函数集合）。因此不对称：

✓ 2n² = O(n³)　　✗ O(n³) = 2n²

在表达式内部，O(...) 表示"某个属于该集合的匿名函数”。2n² + Θ(n) 意为 2n² + f(n)，其中 f ∈ Θ(n)。

误用 4：多参数下擅自省略

图算法是 O(V + E)，不是 O(V)，也不是 O(E)。两个独立参数时不能假设谁支配谁：稀疏图 E = Θ(V)，稠密图 E = Θ(V²)，结论完全不同。见第 21 讲。

四、增长率层级

从慢到快（每一行都是下一行的 o）：

1 ≺ log log n ≺ log n ≺ log²n ≺ √n ≺ n ≺ n log n ≺ n² ≺ n³ ≺ 2ⁿ ≺ n! ≺ nⁿ

复杂度	名称	n 翻倍时	典型来源
Θ(1)	常数	不变	数组下标、散列查找（期望）
Θ(α(n))	反 Ackermann	几乎不变（≤ 4）	并查集（第 23 讲）
Θ(log n)	对数	加 1	二分查找、平衡树
Θ(√n)	平方根	×1.41	分块、试除判素
Θ(n)	线性	×2	遍历、计数排序
Θ(n log n)	线性对数	略多于 ×2	比较排序、MST
Θ(n²)	平方	×4	所有二元组、朴素 DP
Θ(n³)	立方	×8	朴素矩阵乘法、Floyd-Warshall
Θ(2ⁿ)	指数	平方	枚举子集
Θ(n!)	阶乘	—	枚举排列

⭐ “n 翻倍时"这一列是最实用的判据：不用读代码，把输入翻倍看时间变几倍。变 2 倍是线性，变 4 倍是平方——这是性能排查的第一步。

三条常用事实

（1）对数的底无关紧要。 log_a n = log_b n / log_b a，换底只差常数，所以 O(log n) 不写底。⚠️ 但指数的底极其重要：2ⁿ 与 3ⁿ 之比是 (1.5)ⁿ，不是常数。

（2）任何多项式打败任何多对数：对任意 a, b > 0，log^b n = o(n^a)。log¹⁰⁰ n 也慢于 n^0.01。

（3）任何指数打败任何多项式：对任意 a > 0, b > 1，n^a = o(bⁿ)。

五、常用求和与近似

算术级数：   1 + 2 + … + n          = n(n+1)/2          = Θ(n²)
平方和：     1² + 2² + … + n²        = n(n+1)(2n+1)/6    = Θ(n³)
等比 (r<1)： 1 + r + r² + …         = 1/(1-r)           = Θ(1)
等比 (r>1)： 1 + r + … + rⁿ         = (r^(n+1)-1)/(r-1) = Θ(rⁿ)
调和级数：   Hₙ = 1 + 1/2 + … + 1/n = ln n + γ + O(1/n) = Θ(log n)
Stirling：   n! ≈ √(2πn)·(n/e)ⁿ  ⟹  log(n!) = Θ(n log n)

⭐ 两条直觉规则：

等比级数被最大项支配：几何和 ≈ 常数 × 最大项。递归树分析天天用（第 3 讲）。
调和级数是对数级：“第 i 步做 n/i 次工作"总量是 Θ(n log n)——快排、跳表、随机化算法的分析都会遇到。

log(n!) = Θ(n log n) 直接给出比较排序下界（第 12 讲）。

六、怎么从代码读出复杂度

规则 1：顺序语句取最大。 A; B 的代价是 max(cost(A), cost(B))。

规则 2：嵌套循环相乘——仅当内层次数与外层无关。

for i = 1 to n:            for i = 1 to n:
    for j = 1 to n:            for j = i to n:
        O(1)                       O(1)
  ⟹ Θ(n²)                   ⟹ Σ(n-i+1) = Θ(n²)   同为 n²，但要算和

规则 3：看变量怎么变化，别看循环写法。

i = 1                      for i = 1 to n:
while i < n:                   j = 1
    i = i * 2                  while j < n:
  ⟹ Θ(log n)                       j = j * 2
                             ⟹ Θ(n log n)

规则 4：调和和陷阱。

for i = 1 to n:
    for j = i to n step i:     # 内层跑 n/i 次
        O(1)
  ⟹ Σᵢ n/i = n·Hₙ = Θ(n log n)      不是 Θ(n²)

这正是埃拉托色尼筛的复杂度来源（只对素数 i 执行时进一步降为 Θ(n log log n)）。

七、渐近分析骗你的时候

情况	说明
常数巨大	Fibonacci 堆理论优于二叉堆，但常数大、缓存不友好，实测常常更慢
n 很小	标准库排序在 n < 16 时切插入排序
缓存局部性	数组与链表遍历都是 Θ(n)，实测可差 10 倍以上（第 5 讲）
摊还 vs 单次	动态数组 push 摊还 O(1)，但某一次是 Θ(n)——实时系统里可能致命（第 4 讲）
分布敏感	散列表期望 O(1) 依赖散列质量；对抗输入下退化为 Θ(n)（第 7 讲）

⭐ 正确态度：渐近分析用来排除坏方案，实测用来在好方案中选择。

随堂自测

用定义证明 3n² + 10n + 7 = Θ(n²)，给出具体的 c₁、c₂、n₀。
2^(n+1) = O(2ⁿ) 成立吗？2^(2n) = O(2ⁿ) 呢？分别说明理由。
为什么"插入排序的最坏运行时间是 O(n²)“和"插入排序是 O(n²)“都对，但"插入排序是 Θ(n²)“要加限定？
按增长率排序：n log n、2^(log₂ n)、log(n!)、4^(log₂ n)、n^(1/log₂ n)、n!。

下面的循环是什么复杂度？

for i = 1 to n:
    j = i
    while j > 0: j = j / 2

n 从 10⁵ 增到 2×10⁵，时间从 3 s 增到 12.5 s。最可能的复杂度是什么？
为什么 O(log n) 不写底数，而 O(2ⁿ) 的底不能省略？

一、为什么要丢掉常数#

二、三个记号的精确定义#

O：渐近上界#

Ω：渐近下界#

Θ：渐近紧确界#

严格记号 o 与 ω#

三、四个必须避免的误用#

误用 1：把 O 当成"就是这么快"#

误用 2：把「最坏情况」当成「上界」#

误用 3：等号是滥用记号#

误用 4：多参数下擅自省略#

四、增长率层级#

三条常用事实#

五、常用求和与近似#

六、怎么从代码读出复杂度#

七、渐近分析骗你的时候#

随堂自测#