渐进分析:大 O、大 Ω 与大 Θ
一、三种记号各自承诺了什么
这一篇对应官方 Lecture 13(Asymptotics I)与 Lecture 15(Asymptotics II)。
先摆出最容易被误用的那句话:大 O 不是最坏情况。
O(N) 的意思只是「开销的增长速度不超过 N 的某个常数倍」。它在描述上界:
- 一个
Θ(N log N)的算法当然也满足O(N²),因为N log N的增长确实不超过N²。 - 说「这个算法是 O(N²)」可能是真的,但信息量很小。
要让复杂度描述有用,得区分三个记号。
二、三个记号各自承诺什么
| 记号 | 含义 | 通俗说法 | 数学表述 |
|---|---|---|---|
O(f(N)) |
增长不快于 f |
上界 | 存在 c、N₀,当 N > N₀ 时 g(N) ≤ c·f(N) |
Ω(f(N)) |
增长不慢于 f |
下界 | 存在 c、N₀,当 N > N₀ 时 g(N) ≥ c·f(N) |
Θ(f(N)) |
增长恰好是 f 的量级 |
紧确界 | 同时满足上界与下界 |
一张图说清它们的包含关系:
flowchart TB
A["g(N) 的实际增长"] --> B["O(f):把 f 取大一点,总能罩住 g<br/>例:3N 也是 O(N^2)"]
A --> C["Ω(f):把 f 取小一点,总能被 g 罩住<br/>例:N^2 也是 Ω(N)"]
A --> D["Θ(f):两边都夹住,才是最精确的描述<br/>例:3N + 5 是 Θ(N)"]
所以在工程表达里,Θ 才是我们真正想说的话,O 常常被当成 Θ 用,这是一种历史习惯,但推导时必须分清。
三、化简:只留增长最快的项
渐进分析只关心 N → ∞ 时的增长率,所以两件事可以做:丢掉常数因子、丢掉低阶项。
1 | public class GrowthCount { |
输出:
1 | O(N) N=1024 -> 操作数 1024 |
第二行是值得记住的对照:1024 × 10 = 10240。外层循环 k /= 2 从 1024 降到 1 正好 10 次,也就是 log₂N;内层跑满 N 次,两者相乘就是 N log N。
N = 1024 时 N log N ≈ 10N,看起来只比线性慢十倍;但 N 涨到一百万时,log₂N ≈ 20,N log N 就是 20N。log N 涨得极慢,这也是为什么 log 因子在实践中几乎可以忽略,却不能丢——它决定了「先排序再处理」和「直接处理」是不是同一个量级。
四、递归关系:T(N) = 2T(N/2) + N
循环好数,递归难数。归并排序的代价可以写成:
1 | T(N) = 2·T(N/2) + N |
含义是:把规模减半的问题解两遍,再花线性时间把结果合并。用计数程序实测:
1 | public class RecursionCount { |
输出:
1 | n = 64 -> 总代价 384,n log2 n = 384 |
四行全部精确相等。这不是巧合:取 N 为 2 的幂时,递归树有 log₂N 层,每层总代价恰好是 N,乘积就是 N log₂N。递归关系推出的结果与实测数值一模一样,这是理解 O(N log N) 最直接的方式。
递归树的样子:
flowchart TB
R["N"] --> A["N/2"] --> B["N/4 ..."]
R --> C["N/2"] --> D["N/4 ..."]
B --> E["每层合计 = N"]
D --> E
E --> F["共 log2(N) 层"]
F --> G["总代价 = N log2 N"]
五、用「翻倍」验证增长阶
判断一个复杂度是否说对了,最实用的手法是:让 N 翻倍,看代价翻几倍。
1 | public class ScaleCheck { |
输出:
1 | N O(N) O(N log N) O(N^2) |
第三列从 4000 到 9000 是 2.25 倍,从 9000 到 20000 是 2.22 倍。比 2 倍多一点,因为 log N 也在涨,但它涨得足够慢,指数部分始终被 N 主导。这一列就是 O(N log N) 的指纹。
六、隐藏的常数代价
有几处代价在源码里看不见,但会毁掉复杂度:
- 字符串拼接。
s = s + c每次都新建字符串,循环N次就是O(N²)。应改用StringBuilder。 substring与其他复制型操作。 每次调用都产生新数组,写在循环里就变成隐藏的乘积。- 自动装箱。
List<Integer>里每次读写都要在int与Integer之间转换,常数因子可观。 - 递归的栈开销。 时间是
O(N),空间可能是O(N)(递归深度)。
七、小结
| 概念 | 一句话 | 证据 |
|---|---|---|
| 大 O | 只承诺上界,不是最坏情况 | 3N 也是 O(N²) |
| 大 Ω / 大 Θ | 下界 / 紧确界 | 3N + 5 是 Θ(N) |
| 化简 | 丢常数因子与低阶项 | O(2N) 即 O(N) |
| 递归关系 | T(N) = 2T(N/2) + N → Θ(N log N) |
实测 384 / 896 / 2048 / 4608 全等于 n log₂n |
| 翻倍验证 | N 翻倍后代价翻几倍,就是增长阶的证据 |
N log N 列翻约 2.2 倍 |
| 隐藏代价 | 拼接、复制、装箱都在循环里叠乘 | s = s + c 是 O(N²) |
三条能带走的:
Θ才是想说的话,O只是习惯用法。 严格推导时先问「这是上界、下界还是紧确界」。- 递归关系的解法就是画递归树:每层的代价 × 层数。
N log N的来源是「log N层、每层N」。 - 用「翻倍实验」验证复杂度判断。 理论说不清时,数据会告诉你答案。

