别再背 Big-O：十大时间复杂度模式，其实是五种「工作量生成结构」

短视频里那张「10 大时间复杂度模式」速查图（水印 algomaster.io），点赞 911、收藏 765。但收藏夹不等于记忆，更不等于理解——图给的是十个答案，这篇文章给的是那一个问题：输入每变大一点，工作量以什么结构增长？回答了它，十个模式会自己长出来。

一句话主线：复杂度不是背出来的，是从「工作量如何被生成」的结构里读出来的。 十个模式按生成结构归成五个家族——定位、削减、遍历、配对、枚举——外加一个组合（遍历 × 削减）。认出结构，Big-O 自动出现；此后你看代码就像看化学式，一眼读出它的「增长价态」。

先把那张图的十个模式摆在桌面上（原始出处是 AlgoMaster 的 Big-O 教程，作者 Ashish Pratap Singh，另有新闻信版本）：

#	模式	代码形状	Big-O
1	哈希查找	value = map.get(key)	$O(1)$
2	减半循环	while (n > 1) n = n / 2	$O(\log n)$
3	单循环	for (i = 0; i < n; i++)	$O(n)$
4	顺序循环	两个并列的 for	$O(n + m)$
5	循环 + 二分	for 内做 binarySearch	$O(n \log n)$
6	分而治之	$T(n) = 2T(n/2) + n$	$O(n \log n)$
7	嵌套循环	for 套 for，各跑 n	$O(n^2)$
8	三角形回路	内层 j < i	$O(n^2)$
9	分支递归	$T(n) = T(n-1) + T(n-2)$	$O(2^n)$
10	排列	for (c : choices) permute(rest)	$O(n!)$

十行看着是十个知识点。往下读，你会看到它们只是五个问题的答案。

0. 地基：Big-O 到底在度量什么

三件事必须先钉死，否则后面全部悬空。

第一，Big-O 度量的是增长的阶（order of growth），不是运行时间。 它回答的是”输入从 n 变成 2n，工作量变成几倍”，而不是”这段代码跑几毫秒”。所以它天然机器无关：换一台快 10 倍的机器，只是给所有复杂度乘了个常数，谁也没超过谁。

第二，正因为只关心阶，才有三条化简规则——这三条规则就是全部演算工具，后面每一节都在用它们：

1. 丢常数：$O(2n) = O(n)$，$O(n^2/2) = O(n^2)$；
2. 丢低阶项：$O(n^2 + n) = O(n^2)$，因为 n 够大时低阶项占比趋于零；
3. 结构定运算：代码块顺序执行就相加，嵌套执行就相乘。

第三条是本文的钥匙。十个模式的差别，归根结底是”哪些东西在相乘、哪些在相加、乘数本身怎么长出来”。

第三，一个严谨性脚注：严格定义里 $O$ 是”不超过”（上界），$\Theta$ 才是”恰好是”（紧界）——这个区分是 Knuth 在 1976 年的短文 Big Omicron and Big Omega and Big Theta（SIGACT News 8(2)）里正式立下的。日常口语把 O 当 Θ 用，本文也随俗，但在第 9 个模式（斐波那契）你会看到：这个区分不是学究气，速查图在那里恰好只给了上界。

1. 总览：五个家族，五个问题

家族	核心问题	模式	Big-O
定位	位置能不能直接算出来？	#1 哈希	$O(1)$
削减	每一步扔掉多大比例？	#2 减半循环	$O(\log n)$
遍历	每个元素被摸几次？	#3 单循环、#4 顺序循环	$O(n)$、$O(n+m)$
遍历 × 削减	是不是对每个元素做一次削减？	#5 循环+二分、#6 分治	$O(n \log n)$
配对	要检查多少对？	#7 嵌套循环、#8 三角回路	$O(n^2)$
枚举	要检查多少种可能？	#9 分支递归、#10 排列	$O(2^n)$、$O(n!)$

注意左边那列问题的措辞：比例、次数、对、可能。复杂度分析的全部技能，就是看到代码后问对问题。下面逐个家族推导。

2. 定位家族：O(1) —— 位置是算出来的，不是找出来的

value = map.get(key);

为什么哈希查找不随数据量变慢？因为它根本没有在找。hash(key) % 桶数 是一个纯算术运算：不管表里有 10 条还是 10 亿条数据，这个算式的步数一样。搜索的本质是逐步排除，而哈希跳过了排除——它直接计算出目的地。

深一层：O(1) 是有前提的平均值，不是无条件保证。这个平均 O(1) 站在两根柱子上（CLRS §11.2 的标准结论）：

1. 哈希函数把 key 均匀打散。如果所有 key 撞进同一个桶，桶内退化成链表，查找变成 $O(n)$；
2. 装填因子（元素数/桶数）被控制在常数。这靠扩容搬迁维持，搬迁本身 $O(n)$，但摊到每次插入上是常数——这就是”摊还 O(1)“的含义。

工程上连最坏情况也有人兜底：Java 8 起，HashMap 的单个桶超过 8 个元素就从链表转成红黑树，把最坏查找从 $O(n)$ 压到 $O(\log n)$——这是一个正式的 JDK 改进提案 JEP 180，动机之一就是防御恶意构造碰撞 key 的拒绝服务攻击。

面试里说”哈希是 O(1)“没错；能说出平均、摊还、前提、最坏兜底这四个词，才算掌握。

3. 削减家族：O(log n) —— 问”砍几刀砍到 1”

while (n > 1)
    n = n / 2;

关键问题只有一个：从 n 砍半砍到 1，要砍几刀？设砍 k 刀，则 $n / 2^k = 1$，即

$2^k = n \quad\Rightarrow\quad k = \log_2 n$

手算一遍（n = 16）：16 → 8 → 4 → 2 → 1，恰好 4 刀，$\log_2 16 = 4$。✓

这个数字小得反直觉，值得多算两个：$2^{10} = 1024$，$2^{20} \approx 10^6$，$2^{30} \approx 10^9$。也就是说十亿条数据，砍半只需 30 步。log 就是”指数爆炸的倒放”——正着看翻倍很快，反着看砍半更快。

两个常见疑问，当场接住：

“底数是 2 还是 3，要紧吗？” 不要紧。换底公式 $\log_3 n = \log_2 n / \log_2 3$，差一个常数因子，被规则 1 丢掉。所以 Big-O 里只写 $\log n$，不标底。

“二分搜索也是这个吗？” 是同一个结构：每次比较排除一半搜索空间。1000 个元素的有序数组，最多 $\lfloor\log_2 1000\rfloor + 1 = 10$ 次比较必然命中或确认不存在。但注意它的前提——数组有序。有序不是白来的（往下看第 5 节：排序本身要 $n \log n$）。二分的快，是拿排序时”预付”的工作换的。这是一个典型的复杂度转移：把成本从查询时刻挪到准备时刻。

识别特征：循环变量不是 i++ 而是 i *= 2、i /= 2，或者搜索区间每轮缩固定比例——看到”按比例削减”，就是 log。

4. 遍历家族：O(n) 与 O(n+m) —— 加法和乘法的分水岭

for (i = 0; i < n; i++)
    sum += a[i];

单循环没什么可说的：每个元素摸常数次，$n$ 个元素就是 $O(n)$。真正的考点在第 4 个模式：

for (i = 0; i < n; i++) { ... }   // 第一段
for (j = 0; j < m; j++) { ... }   // 第二段

两个循环并列（顺序执行），用加法：$O(n + m)$。如果第二个循环嵌在第一个里面（对每个 i 都完整跑一遍 j），才用乘法：$O(n \times m)$。模式 #4 和模式 #7 的全部区别，就是这一条”顺序相加、嵌套相乘”。

为什么 O(n+m) 不能偷懒写成 O(n)？因为 n 和 m 是两个独立变量，你无法承诺谁大。如果 m 可能远大于 n（比如图算法里顶点数 V 和边数 E，稠密图 E 可达 V²），把 m 吞掉就是错的。BFS/DFS 写 $O(V + E)$ 而不是 $O(V)$，就是这个原因。只有当你能证明 $m \le c \cdot n$（m 被 n 常数倍压住）时，$O(n+m)$ 才塌缩成 $O(n)$。

这一条也是读复杂度表达式的通用规则：表达式里每保留一个变量，就是作者在告诉你”这个量独立地影响成本”。

5. 组合家族：O(n log n) —— 同一个量的两条生成路径

$n \log n$ 有意思的地方在于：它不是一个新家族，而是遍历 × 削减的乘积，且有两条完全不同的路径都长出它。

路径一（模式 #5）：外层遍历，内层削减。

for (i = 0; i < n; i++)
    binarySearch(a, x[i]);   // 每次 O(log n)

n 个元素，每个做一次 $\log n$ 的二分：$n \times \log n$。结构一目了然。

路径二（模式 #6）：分治。归并排序的递推式：

$T(n) = 2T(n/2) + n$

翻译成人话：把规模 n 的问题劈成两个规模 n/2 的子问题（$2T(n/2)$），再花 $n$ 的代价合并。它为什么也是 $n \log n$？画递归树，逐层数工作量（n = 8）：

第 0 层:        [8]           → 合并代价 8
第 1 层:      [4] [4]         → 4 + 4 = 8
第 2 层:    [2] [2] [2] [2]   → 2×4 = 8
第 3 层:   [1]×8（递归到底）   → 常数×8

发现规律了吗：每一层的总工作量都恰好是 n——问题被劈得越多，每块越小，加起来不变。而层数就是”8 砍半砍到 1 要几刀”，即 $\log_2 n = 3$ 层。于是：

$\text{总工作量} = \underbrace{n}_{\text{每层}} \times \underbrace{\log_2 n}_{\text{层数}} = O(n \log n)$

两条路径殊途同归：路径一是”n 次循环，每次干 log n 的活”；路径二是”log n 层，每层干 n 的活”。乘法交换律的算法版。更一般的分治递推 $T(n) = aT(n/b) + f(n)$ 由主定理（Master Theorem）统一处理，展开推导可看 AlgoMaster 的主定理讲义或 CLRS 第 4 章——归并排序落在”劈开的代价与合并的代价每层持平”的情形，结论正是 $\Theta(n \log n)$。

深水区：为什么排序偏偏卡死在 n log n

这是全文最值得带走的一段，它把 #5、#6、#10 三个模式串成一条线。

任何基于比较的排序，本质是通过一连串”a 和 b 谁大”的是非题，去确定 n 个元素的真实顺序。n 个元素共有 $n!$ 种可能的排列（这正是模式 #10 的那个 $n!$），排序开始前它们都有嫌疑；每问一个是非题，最多把嫌疑集合砍掉一半（削减家族！）。要从 $n!$ 个嫌疑人砍到 1 个，至少要问：

$\log_2(n!) \text{ 次}$

而由 Stirling 近似，$\log_2(n!) \approx n \log_2 n - 1.44n$，主项就是 $n \log_2 n$。手算验证（n = 64）：$\log_2(64!) \approx 296$，而 $n \log_2 n = 64 \times 6 = 384$——同一个数量级。✓ 这就是 CLRS §8.1 那个著名定理（任何比较排序最坏情况需要 $\Omega(n \log n)$ 次比较）的直觉版。

看清这条线了吗：$n!$ 是”所有可能的顺序”，$\log$ 是”逐步砍半排除”，$n \log n$ 就是用是非题从 $n!$ 种可能里锁定真相的信息代价。归并排序摸到了这条理论地板，所以说它”最优”；而桶排序、基数排序能跑 $O(n)$，不是推翻了定理，而是它们不靠比较——换了游戏规则。

6. 配对家族：O(n²) —— 数”对”，不数”个”

// #7 嵌套循环：全网格
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) { ... }

// #8 三角形回路
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++) { ... }

嵌套循环用乘法：外层每转一格，内层完整跑一遍，$n \times n = n^2$。它对应的问题是”所有有序对都要检查一遍”。

三角回路呢？内层只跑到 j < i，直觉上”少了一半，会不会降阶？“精确地数：i = 0 时内层跑 0 次，i = 1 时跑 1 次……i = n−1 时跑 n−1 次，总计

$0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}$

手算验证（n = 6）：$0+1+2+3+4+5 = 15 = \frac{6 \times 5}{2}$。✓ 这就是高斯求和，也正是”n 个人两两握手要握几次”的答案——三角回路检查的是所有无序对。

展开 $\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$：规则 2 丢掉 $\frac{n}{2}$，规则 1 丢掉 $\frac{1}{2}$，剩下 $O(n^2)$。阶没变。“减半”只在削减家族里降阶（因为它是每步按比例砍），在这里只是砍掉一个常数因子——这是初学者最容易混淆的两个”一半”。

但灰度也要讲清：理论上同阶，工程上 n = 100 时全网格是 10,000 次、三角是 4,950 次，真实时间差一倍。Big-O 决定算法能不能用，常数因子决定它好不好用——两件事都真实，只是分属不同层。

识别特征：内层循环变量依赖外层（j < i、j = i+1）→ 无序对，三角；互不依赖 → 有序对，全网格。都是 $\Theta(n^2)$。

7. 枚举家族：O(2ⁿ) 与 O(n!) —— 也是全图唯一需要纠偏的地方

前四个家族的工作量随 n 多项式增长；枚举家族不同，它的问题是”要检查多少种可能”，而可能性是相乘累积的——每多一个元素，可能性翻倍甚至翻 n 倍。

模式 #9：分支递归——以及速查图没告诉你的 φ

$T(n) = T(n-1) + T(n-2)$

这是不带记忆化的斐波那契递归。为什么是指数？看调用树：每个节点分裂成两个子调用，树深约 n，满二叉树有 $2^n$ 个节点——所以 $O(2^n)$。

但这里正是 O 与 Θ 的区分动真格的地方。这棵树并不满：左子树深 n−1、右子树只深 n−2，右边总是先到底。紧界要解递推式——设 $T(n) = x^n$ 代入，得特征方程：

$x^2 = x + 1 \quad\Rightarrow\quad x = \frac{1+\sqrt{5}}{2} = \varphi \approx 1.618$

黄金分割率。真实增长是 $\Theta(\varphi^n) \approx \Theta(1.618^n)$，不是 $2^n$。差多少？手算（n = 30）：fib(30) 的实际调用次数是 $2F(31) - 1 = 2{,}692{,}537 \approx 270$ 万；而 $2^{30} \approx 10.7$ 亿——上界比紧界虚了约 400 倍。速查图写 $O(2^n)$ 没有错（O 本来就是上界），但若追问”到底多快”，答案是 $\varphi^n$。面试中能指出这一点，是从”背过”到”推过”的分界线。

还有一句必须说的逃生通道：这个 $\varphi^n$ 慢，不是问题固有的，是这种写法固有的。加一行记忆化（缓存已算过的 fib(k)），不同的子问题只剩 n 个，复杂度瞬间从指数塌缩到 $O(n)$。复杂度是算法的属性，不是问题的属性——同一个问题换个算法，可以差出天文数字。这也是把速查图当”判决书”最危险的地方：它描述的是”当前这种代码形状”的代价，不是问题的宿命。

模式 #10：排列——增长率的天花板

void permute(List<T> rest) {
    for (T c : rest)          // 第一格有 n 种选择
        permute(rest - c);    // 第二格剩 n-1 种……
}

生成全排列：第一个位置 n 种选法，第二个位置剩 n−1 种，一路乘下去：

$n \times (n-1) \times \cdots \times 1 = n!$

它比 $2^n$ 还猛得多——$2^n$ 是每步固定翻 2 倍，$n!$ 是第 k 步翻 (n−k) 倍，越前面的分支越粗。感受一下规模：$10! \approx 363$ 万（一秒内能跑完）；$20! \approx 2.4 \times 10^{18}$，按每秒 $10^8$ 次操作算要七百多年。这就是为什么旅行商问题暴力解 20 个城市就已经宣告死刑。

顺带一提，你已经在第 5 节见过 $n!$ 了——它是”n 个元素所有可能顺序”的总数。排序的伟大就在于：面对 $n!$ 种可能，它用 $\log_2(n!) \approx n\log n$ 次比较就锁定了答案，指数级的可能性空间，被对数武器削成了准线性。枚举家族和削减家族，是同一枚硬币的两面。

8. 实战换算：从数据规模反推可用复杂度

分析出复杂度只是前半程；工程和竞赛里更常用的是反向操作——看一眼输入规模，直接推出你被允许用什么算法。桥梁是一条经验法则：现代机器每秒大约执行 $10^8$ 次简单操作（保守估计，常数好的代码可到 $5 \times 10^8$）。这张对照表来自 USACO Guide，与 Laaksonen《Competitive Programmer’s Handbook》第 2 章的版本一致：

输入规模 n	可接受的复杂度
n ≤ 10	$O(n!)$、$O(n^7)$、$O(n^6)$
n ≤ 20	$O(2^n \cdot n)$、$O(n^5)$
n ≤ 80	$O(n^4)$
n ≤ 400	$O(n^3)$
n ≤ 7500	$O(n^2)$
n ≤ 7 × 10⁴	$O(n\sqrt{n})$
n ≤ 5 × 10⁵	$O(n \log n)$
n ≤ 5 × 10⁶	$O(n)$
n ≤ 10¹⁸	$O(\log^2 n)$、$O(\log n)$、$O(1)$

验算两行让它可信（n = $10^6$）：$n \log_2 n \approx 10^6 \times 20 = 2 \times 10^7$ 次操作 → 0.2 秒，稳过 ✓；$n^2 = 10^{12}$ 次 → 约 2.8 小时，判死刑 ✗。

这张表把前面七节接上了电：题目说 n ≤ 20，等于明示你”枚举家族（$2^n$）可以上”；说 n ≤ $10^5$，等于要求你至少造出 $n \log n$——也就是必须在遍历之上叠一层削减。约束条件是出题人写给你的密电码。

9. 收束：一棵识别决策树

把五个家族折叠成看代码时的问题序列：

flowchart TD
    A[看到一段代码] --> B{有递归自调用吗?}
    B -- 没有 --> C{循环怎么组织?}
    B -- 有 --> D{每次递归派生几个子调用?}
    D -- "1 个, 且规模按比例砍" --> E["削减: O(log n)"]
    D -- "2 个, 规模砍半, 合并花 O(n)" --> F["分治: O(n log n)"]
    D -- "2 个, 规模只减 1 或 2" --> G["分支递归: O(2ⁿ) 级"]
    D -- "n 个, 逐层减 1" --> H["排列: O(n!)"]
    C -- 没有循环, 直接计算位置 --> I["定位: O(1)"]
    C -- "单层, i++ 步进" --> J["遍历: O(n)"]
    C -- "单层, i*=2 或 i/=2" --> E
    C -- 两个循环并列 --> K["相加: O(n+m)"]
    C -- "两层嵌套, 都步进" --> L["配对: O(n²)"]
    C -- "外层步进 × 内层砍半" --> M["组合: O(n log n)"]

以及三条比图更重要的元规则，它们能处理图之外的一切变体：

1. 顺序相加，嵌套相乘——结构决定运算；
2. 按比例削减出 log，按步长递减不出——两种”变小”泾渭分明；
3. 复杂度是算法的属性，不是问题的属性——换表示、加缓存、改规则（如基数排序），阶可以被击穿。

10. 自测：四段代码，先答再翻

① 这段是多少？
for (int i = 1; i < n; i *= 2)
  for (int j = 0; j < n; j++) work();

外层是削减结构（i *= 2，跑 $\log_2 n$ 轮），内层是遍历（n 次），嵌套相乘：$O(n \log n)$。注意和模式 #5 对照——这里是”削减套遍历”，#5 是”遍历套削减”，乘法交换律，同阶。

② 数组 a 长 n、b 长 m，先各自排序，再一次线性合并，总复杂度？

$O(n \log n + m \log m + n + m)$，化简后 $O(n \log n + m \log m)$。三段顺序执行用加法；且 n、m 独立，不能互吞。若题目额外保证 $m \approx n$，才可写成 $O(n \log n)$。

③ 求一个集合的所有子集（每个元素选/不选，递归到底），多少？

每层两个分支（选 / 不选），深度 n，且两个分支的子问题规模都只减 1——树是满的，恰好 $2^n$ 个叶子：$\Theta(2^n)$。对比斐波那契：那棵树不满所以紧界掉到 $\varphi^n$，这棵是满的，$2^n$ 就是紧界。

④ for (int i = 0; i < n; i++) if (set.contains(a[i])) count++;（set 是 HashSet）

遍历（n 次）× 定位（平均 $O(1)$）= 平均 $O(n)$。完整的回答要带上第 2 节的前提：哈希均匀、装填因子受控时成立；对抗性输入下最坏可退化（Java 8 后单桶树化兜底到 $O(n \log n)$ 总体）。

四题全对，且每题都能说出”用了哪条元规则”，这张速查图就可以从收藏夹里删掉了——它已经搬进你脑子里了。

参考来源

原图与教程

• Big O Notation: Introduction — AlgoMaster.io（速查图内容的原始出处，作者 Ashish Pratap Singh）
• Big-O Notation: Explained in 8 Minutes — AlgoMaster Newsletter
• Master Theorem — AlgoMaster.io

教科书与论文

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms（CLRS）：§8.1 比较排序的 $\Omega(n \log n)$ 下界；§11.2 哈希表平均情形分析；第 4 章主定理
• D. E. Knuth, Big Omicron and Big Omega and Big Theta, ACM SIGACT News 8(2), 1976（O/Ω/Θ 记号的正名之作）
• Antti Laaksonen, Competitive Programmer’s Handbook, 第 2 章 Time Complexity（规模→复杂度对照表）

工程实践

• JEP 180: Handle Frequent HashMap Collisions with Balanced Trees — OpenJDK（Java 8 HashMap 桶树化，最坏 $O(n) \to O(\log n)$）
• Time Complexity — USACO Guide（$10^8$ 次操作/秒经验值与完整对照表）