1.8 渐近复杂度分析

前面七篇，我们一直在用 $O(n^2)$、$O(n\log n)$、$O(V+E)$ 这些记号，也多次说了"最好情况""最坏情况""平均情况"。这一篇和下一篇，是专门把这套分析语言讲透。它们不教新算法，但教你怎么严格地衡量一个算法——这是后面所有卷的基础设施。本篇讲渐近复杂度，下一篇讲循环不变量（证明正确性）。

1.为什么需要一套记号

我们已经会用 $O(\cdot)$ 了，但要认真做分析，光一个 $O$ 不够。考虑两个问题：归并排序最坏 $O(n\log n)$，但这只告诉我们"上界是 $n\log n$"；我们有时候还想说"它至少要 $\Omega(n\log n)$"（下界），甚至"它恰好是 $\Theta(n\log n)$"（紧界）。这三种说法强度不同，需要三套记号。

2.三个记号：$O$、$\Omega$、$\Theta$

设 $f(n)$ 是算法的真实代价，$g(n)$ 是一个简洁的参照函数（如 $n^2$、$n\log n$）。

大 O（上界）。 $f(n)=O(g(n))$ 表示：存在常数 $c>0$ 和 $n_0$，对所有 $n\ge n_0$ 有 $0\le f(n)\le cg(n)$。直觉：$f$ 增长得不会比 $g$ 快。用来表达"最坏情况下封顶在 $g$"。

大 Ω（下界）。 $f(n)=\Omega(g(n))$ 表示：存在 $c>0$、$n_0$，对所有 $n\ge n_0$ 有 $0\le cg(n)\le f(n)$。直觉：$f$ 至少增长得和 $g$ 一样快。用来表达"再怎么优化也快不过 $g$"，或者"这个问题的任何算法都至少要 $g$ 这么多"（下界证明）。

大 Θ（紧界）。 $f(n)=\Theta(g(n))$ 当且仅当同时 $f(n)=O(g(n))$ 且 $f(n)=\Omega(g(n))$。直觉：$f$ 和 $g$ 同阶，增长趋势精确吻合。这是最强的说法——既封顶又托底。

三者的关系记一句话：$O$ 是天花板，$\Omega$ 是地板，$\Theta$ 是天花板和地板刚好相等（精确拟合）。 工程里最常说"$O(n^2)$"是图省事（其实往往能证到 $\Theta(n^2)$）；做严格分析时，能证 $\Theta$ 就别只说 $O$，因为它信息最完整。

忽略常数和低阶项。 三个记号都只看渐近（$n\to\infty$），所以常数系数、低阶项统统忽略：$3n^2+5n+7=\Theta(n^2)$。为什么能忽略？因为 $n$ 足够大时，$n^2$ 项碾压 $5n$ 和 7，它们对增长趋势的贡献趋于 0。这也是渐近分析的核心取舍：牺牲小规模的精度，换来对大规模趋势的精确刻画。

3.最好、最坏、平均

同一个算法，代价可能随输入变化。插入排序就是活教材：

• 最好（输入已序）：$O(n)$。
• 最坏（输入逆序）：$\Theta(n^2)$。
• 平均（随机输入）：$\Theta(n^2)$（常数是最坏的一半，但同阶）。

严格分析要分开讨论这三种。其中：

• 最坏情况最常被引用，因为它给出"不管输入多差，都封顶在这儿"的保证。实时系统、安全相关场景只信最坏。
• 平均情况更贴近日常体感，但需要假设输入的概率分布（通常假设均匀随机），有时这个假设不成立（比如输入可能被恶意构造——哈希表碰撞攻击就是反例）。
• 最好情况一般不用来评价算法（太乐观），但有时用来对比。

第四卷会讲摊还分析（4.3），那是处理"单次操作偶尔很贵、但整体平均便宜"的更精细工具（比如动态数组扩容），和这里的平均分析不一样，到时候区分。

4.常见的渐近阶

把这些阶从慢到快（即从便宜到贵）排好，要烂熟于心：

$$O(1)\ <\ O(\log n)\ <\ O(\log^2 n)\ <\ O(\sqrt n)\ <\ O(n)\ <\ O(n\log n)\ <\ O(n^2)\ <\ O(n^3)\ <\ O(2^n)\ <\ O(n!)$$

每个的直觉，结合前面的算法对号入座：

• $O(1)$：哈希表平均查找；数组按下标取值。
• $O(\log n)$：二分查找（1.3）；平衡树操作。
• $O(n)$：BFS/DFS 遍历图（$O(V+E)$）；线性扫描。
• $O(n\log n)$：归并排序（1.2）、堆排序（1.4）；FFT（第二卷）。
• $O(n^2)$：插入排序最坏（1.1）；朴素矩阵乘法的一个维度。
• $O(n^3)$：朴素矩阵乘法（三个嵌套循环）；Floyd-Warshall（第五卷）。
• $O(2^n)$、$O(n!)$：枚举所有子集/排列，组合爆炸，基本不可行。

$O(n\log n)$ 是个分水岭：比它便宜的（$O(n)$、$O(\log n)$）通常意味着你利用了某种结构（有序、哈希）；比它贵的（$O(n^2)$ 及以上）往往意味着你在做不必要的重复工作。排序的下界是 $\Omega(n\log n)$（4.9 节决策树下界会证），所以 $O(n\log n)$ 的归并/堆排序已经是最优的排序了——不可能有基于比较的排序做到 $O(n)$。

5.递归复杂度：递归树直觉

分治算法的复杂度靠递归关系表达，比如归并排序的 $T(n)=2T(n/2)+\Theta(n)$。怎么从递归关系求出 $T(n)$ 的闭式？最直观的工具是递归树（4.1 节详讲，这里给直觉）。

画一棵树：根节点是原问题代价，每个子节点是一个子问题代价，逐层展开。把每层代价加起来，再把所有层加起来，就是总代价。

拿 $T(n)=2T(n/2)+\Theta(n)$ 举例：

• 第 0 层：1 个规模 $n$ 的问题，代价 $\Theta(n)$。
• 第 1 层：2 个规模 $n/2$ 的子问题，代价 $2\cdot\Theta(n/2)=\Theta(n)$。
• 第 2 层：4 个规模 $n/4$ 的子问题，代价 $4\cdot\Theta(n/4)=\Theta(n)$。
• …每层代价都是 $\Theta(n)$。
• 共 $\log_2 n$ 层（规模每次减半，$n\to 1$ 要 $\log_2 n$ 次）。

总代价 $=\Theta(n)\times \log_2 n=\Theta(n\log n)$。这就是归并排序 $O(n\log n)$ 的严格来历。

第四卷的主定理（4.2）会给出一类形如 $T(n)=aT(n/b)+f(n)$ 的递归的通用解法，不用每次画树。但现在你要掌握递归树这个直觉工具——它是理解主定理的基础。

6.一个易错点：$n$ 到底是谁

读复杂度时永远先问一句：这里的 $n$ 代表什么？ 同一个算法，换个"$n$"的定义，复杂度式子就不同。

• 图算法里 $O(V+E)$：$V$ 是顶点数，$E$ 是边数。稀疏图（$E\approx V$）和稠密图（$E\approx V^2$）差别巨大，光说 $O(V^2)$ 会误导。
• 矩阵乘法 $O(n^3)$：$n$ 是矩阵边长，不是元素个数（元素个数是 $n^2$）。如果按元素个数 $N=n^2$ 来写，就是 $O(N^{3/2})$，面目全非。
• 字符串匹配 $O(nm)$：$n$ 是文本长度，$m$ 是模式长度，两个不同的量。

养成习惯：写复杂度时标注清楚每个符号的含义，读别人的复杂度时也先确认符号定义，这是避免误判的第一步。

7.练习

Q1. $O$、$\Omega$、$\Theta$ 分别表达什么？为什么说 $\Theta$ 信息最完整？

$O$ 是上界（封顶）、$\Omega$ 是下界（托底）、$\Theta$ 是紧界（同时 $O$ 和 $\Omega$，即精确同阶）。$\Theta$ 最完整因为它既保证了"不会比 $g$ 快"又保证了"不会比 $g$ 慢"，把代价精确钉死在 $g$ 这一阶。说"算法是 $\Theta(n\log n)$"比说"$O(n\log n)$"信息多——后者可能是 $\Theta(n)$ 也可能是 $\Theta(n\log n)$，前者是确定的。

Q2. 用递归树论证 $T(n)=4T(n/2)+\Theta(n)$ 的解。

第 0 层 1 个 $n$，代价 $\Theta(n)$；第 1 层 4 个 $n/2$，代价 $4\cdot\Theta(n/2)=\Theta(2n)$；第 $i$ 层 $4^i$ 个 $n/2^i$，代价 $\Theta(2^i n)$。每层代价在翻倍。共 $\log_2 n$ 层。总代价是个等比级数，被最后一层（叶子层 $4^{\log n}=n^2$ 个）主导，所以 $T(n)=\Theta(n^2)$。注意这和归并排序不同——归并是 $2T(n/2)$，叶子数 $n$；这里是 $4T(n/2)$，叶子数 $n^2$，所以贵得多。

Q3.（思考题） 为什么说"基于比较的排序不可能比 $O(n\log n)$ 更快"？这和渐近分析有什么关系？

4.9 节会用决策树下界严格证明：$n$ 个元素有 $n!$ 种排列，比较排序每次比较（叶子）最多把可能性砍半，所以决策树至少要 $\log_2(n!)=\Theta(n\log n)$ 层。这是个 $\Omega(n\log n)$ 的下界——任何比较排序都至少要这么多。渐近分析里的下界证明，回答的正是"为什么某些问题无法更快"，这是第四卷的核心主题之一。

8.小结

渐近分析是衡量算法的语言。$O$/$\Omega$/$\Theta$ 三件套分别表达上界、下界、紧界；最好/最坏/平均区分不同输入下的表现；递归树是求解分治复杂度的直觉工具。记住"忽略常数、只看趋势"和"先问 $n$ 是谁"这两条纪律。下一篇我们用这套语言之外、但同样重要的另一件武器——循环不变量，来证明算法的正确性。