零基础陪读 Big-O：那篇复杂度深读读不动？你缺的是六件初中数学工具

你读《别再背 Big-O》觉得吃力，不是因为概念难，而是因为每个数学符号都是一个压缩包。$T(n) = 2T(n/2) + n$ 是一段话压成的一行；数学熟练的人扫一眼自动解压，不熟练的人每个包都要手动解压——一句话里出现三个包，脑子就满了。这篇陪读做一件事：把原文用到的六件工具逐个拆开、用手算装进你脑子，装好一件就立刻回原文对一次账。读完再回去看原文，公式会自己开口说话。

先把账算清楚。原文假设你能流畅做这六个动作：

#	工具	原文哪里在用它
1	「阶」的眼镜（为什么允许丢常数、丢低阶项）	第 0 节三条化简规则、O 与 Θ 的区分
2	指数（翻倍的世界）	$2^n$、“每级翻倍”
3	对数（指数的倒放）	$k = \log_2 n$、换底公式
4	求和与高斯配对	$0+1+\cdots+(n-1) = \frac{n(n-1)}{2}$
5	乘法原理与阶乘	$n!$、$\log_2(n!) \approx n\log_2 n$
6	递推式怎么读	$T(n)=2T(n/2)+n$、特征方程 $x^2=x+1$

六件都不超过初中水平——难的从来不是知识本身，是它们被压缩后的样子。逐件来。

工具一：「阶」的眼镜——为什么丢常数不是耍流氓

真问题：小明抄写员每分钟抄 50 字，小红每分钟抄 100 字。现在文档从 1 万字涨到 100 万字，谁的处境更糟糕？

答案：一样糟糕。文档涨 100 倍，两人的耗时都恰好涨 100 倍。小红永远比小明快一倍，但”涨价的方式”两人完全相同。

Big-O 关心的就只有”涨价的方式”。用一个手算表看清楚：

n	$n^2$	$n^2/2$	n 翻倍后各自变几倍
10	100	50	—
20	400	200	都是 4 倍
40	1600	800	都是 4 倍

$n^2$ 和 $n^2/2$ 对”n 翻倍”的反应一模一样：都变 4 倍。前面那个 $\frac{1}{2}$ 不改变反应方式，就像小红的”快一倍”不改变涨价方式。所以丢常数：$O(n^2/2) = O(n^2)$。

丢低阶项同理。看 $n^2 + n$ 里那个 $n$ 占多大分量：

n	$n^2 + n$	其中 $n$ 占比
10	110	9.1%
100	10100	0.99%
1000	1001000	0.0999%

n 越大，低阶项占比冲向零。Big-O 本来就只关心”n 很大时”，所以扔掉它不损失任何信息。这两条规则不是约定俗成的偷懒，是”只看涨价方式”这个立场的必然推论。

顺手装好 O、Θ、Ω 三副眼镜——用考试分数说：

• $O$：“他考试不超过 90 分”——上界，天花板；
• $\Omega$：“他至少 90 分”——下界，地板；
• $\Theta$：“他就是 90 分上下这一档”——天花板和地板夹住了，说死了。

说”不超过 90 分”永远安全，哪怕他实际只考 60——但这句话就不紧。

回扣原文：第 0 节的三条化简规则，现在你知道它们为什么合法了。而第 7 节说”速查图写 $O(2^n)$ 没有错，但紧界是 $\varphi^n$“，翻译过来就是：图说了句”fib 不超过 90 分”的安全话，实际上他只考了 60 分（$1.618^n$ 远小于 $2^n$）。O 没说错，只是没说准；Θ 才是说准。

工具二：指数——翻倍的世界有多快

真问题：一张 0.1 毫米厚的纸，对折多少次能厚到月球（38.4 万公里）？

对折一次厚度翻倍：折 k 次就是 $0.1 \text{mm} \times 2^k$。手算试 42 次：

$2^{42} = 2^{10} \times 2^{10} \times 2^{10} \times 2^{10} \times 2^2 \approx 1000^4 \times 4 = 4 \times 10^{12}$

$0.1 \text{mm} \times 4 \times 10^{12} = 4 \times 10^{11} \text{mm} = 40$ 万公里。42 次对折，超过地月距离。（这里用了一个值得单独记住的近似：$2^{10} = 1024 \approx 1000$，所以 $2^{20} \approx$ 百万、$2^{30} \approx$ 十亿。）

反直觉在哪：前 10 折还不到一本书厚（10 厘米），你完全感觉不到威胁；后 10 折每一折都是天文数字级的跳跃。指数增长的危险就是”前期温和得像线性，后期陡得没有任何东西追得上”。

回扣原文：第 7 节说 $2^n$ “20 个城市就宣告死刑”、$T(n)=T(n-1)+T(n-2)$ 的调用树”每个节点分裂成两个”——那棵树就是这张纸：每往深一层节点数翻倍，30 层就是 $2^{30} \approx$ 十亿次调用。你现在对”指数爆炸”有了折纸的体感。

工具三：对数——指数的倒放

真问题：我心里想一个 1 到 1000 之间的数，你每次问一个”是否大于 x”的是非题。最少几次必然猜中？

策略当然是每次砍一半：1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1。数一数，10 刀。为什么是 10？因为你在做折纸的逆运算——折纸问”翻倍几次到 1000”，猜数字问”砍半几次回到 1”，同一个问题：

$2^k \ge 1000 \quad\Rightarrow\quad k = 10 \;(2^{10} = 1024)$

对数就是这个 k 的名字：$\log_2 1000 \approx 10$。定义一句话：$\log_2 n$ = “n 是 2 的几次方” = “n 翻倍几次能到 / 砍半几次归 1”。它不是新运算，是指数的倒放。再手算一个巩固：猜 1~365（猜生日），$2^9 = 512 \ge 365$，9 次够了。

换底公式也当场拆掉。原文说”底数是 2 还是 3 不要紧”，为什么？手算：$\log_8 64 = 2$（因为 $8^2 = 64$），而 $\log_2 64 = 6$。两个答案差 3 倍——而 3 恰好是 $\log_2 8$。规律：换底 = 除以一个固定的数。固定的数就是常数，工具一刚说过：常数被丢掉。所以 Big-O 里 $\log$ 从不标底。

回扣原文：第 3 节的核心推导 $n/2^k = 1 \Rightarrow k = \log_2 n$，就是猜数字游戏的公式化——“砍半砍到 1 要几刀”。第 3 节说”十亿条数据砍半只需 30 步”，就是 $2^{30} \approx 10^9$ 倒过来念。二分搜索 1000 个元素最多 10 次比较——和你刚玩的猜数字是同一个游戏。

工具四：求和号与高斯配对

真问题：6 个人的聚会，每两人握一次手，一共握多少次？

逐个数：第 1 个人和后面 5 人握（5 次），第 2 个人和后面 4 人握（4 次，和第 1 人那次已经算过）……

$5 + 4 + 3 + 2 + 1 = 15$

高斯的算法快在配对：把这串数正着写一遍、倒着写一遍，上下相加：

  5 + 4 + 3 + 2 + 1
+ 1 + 2 + 3 + 4 + 5
= 6 + 6 + 6 + 6 + 6  = 5 × 6 = 30，再除以 2（每个数算了两遍）= 15 ✓

一般化：从 0 加到 n−1，共 n 项，首尾配对每对都是 n−1，所以

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

n = 6 代入：$\frac{6 \times 5}{2} = 15$ ✓。至于 $\sum$ 这个符号——它只是”把一串按规律递增的数加起来”的速记，$\sum_{i=0}^{n-1} i$ 读作”i 从 0 数到 n−1，全加起来”，就是上面那行加法，没有任何新内容。

回扣原文：第 6 节三角回路的计数”i=0 时内层跑 0 次，i=1 时跑 1 次……总计 $\frac{n(n-1)}{2}$“——每一圈外层循环就是一个人在握手，内层 j < i 就是”只和排在自己前面的人握”。握手 = 无序对 = 三角回路，一个东西的三个名字。

工具五：乘法原理与阶乘——以及”猜排列”游戏

真问题一：3 件上衣、2 条裤子，有几种穿搭？

每件上衣都能配 2 条裤子：$3 \times 2 = 6$ 种。这就是乘法原理：分步骤做的事，方案数相乘。

真问题二：5 个人排队照相，有几种排法？

第 1 个位置 5 种选择，选定后第 2 个位置剩 4 种，然后 3、2、1：

$5 \times 4 \times 3 \times 2 \times 1 = 120$

这个”从 n 一路乘到 1”就是阶乘 $n!$。感受它的凶残：$4! = 24$，$5! = 120$，$10! = 3628800$——每多一个人，方案数乘一个越来越大的数。对比指数：$2^n$ 每步固定 ×2，$n!$ 第一步就 ×n。这就是为什么原文说 $n!$ 是”增长率的天花板”。

真问题三（全文最妙的一步，慢慢走）：5 个人排好了队但用布挡住，你只能问是非题（“甲在乙前面吗？”），最少问几次能完全确定队形？

队形共 $5! = 120$ 种可能。每个是非题最好情况下把可能性砍一半——这是工具三的猜数字游戏！从 120 砍到 1 要几刀：

$2^7 = 128 \ge 120 \quad\Rightarrow\quad 7 \text{ 次}$

也就是 $\log_2(5!) \approx 6.9$，向上取整 7。现在你已经自己发明了排序下界定理：排序就是”通过比较（是非题）确定 n 个元素的真实队形”，队形有 $n!$ 种，所以至少要比较 $\log_2(n!)$ 次。

回扣原文：第 5 节”深水区”那段——“n 个元素共有 $n!$ 种可能的排列……每问一个是非题最多把嫌疑集合砍掉一半……至少要问 $\log_2(n!)$ 次”——就是这个 5 人排队游戏放大到 n 人。而 $\log_2(n!) \approx n\log_2 n$（Stirling 近似）你不需要会推，只需要手感：$\log_2(n!) = \log_2 n + \log_2(n-1) + \cdots$，共 n 项、每项不超过 $\log_2 n$，所以总和在 $n \log_2 n$ 这个量级。原文 n=64 的验算（296 对 384）就是在展示这个手感。

工具六：递推式是压缩的故事——读法与解法

先解决读法。$T(n) = 2T(n/2) + n$ 让人发怵，是因为没人告诉你它是一个故事的压缩。解压出来是三句话：

1. $T(n)$：搞定规模为 n 的问题，总共要干多少活（这是我们想求的未知数）；
2. $= 2T(n/2)$：我的干法是劈成两半，各自搞定（每半的活是 $T(n/2)$，有两份）；
3. $+\, n$：两半各自搞定后，把结果合起来还要干 n 的活。

再解决解法：不用任何技巧，从小到大手算。约定 $T(1) = 0$（单个元素天然有序，不用干活）：

$T(2) = 2T(1) + 2 = 0 + 2 = 2$ $T(4) = 2T(2) + 4 = 4 + 4 = 8$ $T(8) = 2T(4) + 8 = 16 + 8 = 24$

对照公式 $n \log_2 n$：$8 \times \log_2 8 = 8 \times 3 = 24$。严丝合缝。你刚刚用小学算术验证了归并排序的复杂度。原文那棵”每层都是 8”的递归树，就是把这三行竖式画成了图：3 层（$\log_2 8$），每层干 8 的活。

最后拆特征方程——原文第 7 节最陡的一步：为什么解 $T(n) = T(n-1) + T(n-2)$ 要”设 $T(n) = x^n$ 代入”？

思路只有一句话：先猜答案长什么样，再倒推参数。猜”这个数列像等比数列一样增长，每项是前项的 x 倍”，那么 $T(n) = x^n$。代进去：

$x^n = x^{n-1} + x^{n-2}$

两边同除以 $x^{n-2}$（就是约分）：

$x^2 = x + 1$

初中求根公式解出 $x = \frac{1+\sqrt{5}}{2} \approx 1.618$。猜测对不对，拿真数据验：斐波那契数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，算相邻两项的比：

$\frac{34}{21} \approx 1.6190,\quad \frac{55}{34} \approx 1.6176,\quad \frac{89}{55} \approx 1.6182$

比值确实在钉死 1.618。“特征方程”这个吓人的名字，全部内容就是：猜等比、代入、约分、解一元二次。

回扣原文：第 7 节”设 $T(n) = x^n$ 代入，得特征方程 $x^2 = x + 1$，解得 $\varphi \approx 1.618$“——四步你现在每步都走过了。原文说 fib(30) 实际约 270 万次调用而 $2^{30}$ 约 10.7 亿，“上界虚了 400 倍”，就是工具一那句”他说不超过 90 分，实际考了 60”。

终局：逐符号翻译表

带着这张表回去重读原文，遇到卡壳就查：

原文符号/公式	人话翻译	出自哪件工具
$O(f(n))$	”工作量的涨价方式不超过 f(n) 这一档”（天花板）	工具一
$\Theta(f(n))$	”涨价方式就是 f(n) 这一档”（说死了）	工具一
$\Omega(f(n))$	”涨价方式至少 f(n) 这一档”（地板）	工具一
丢常数、丢低阶项	常数不改变”n 翻倍后变几倍”；低阶项占比冲向零	工具一
$2^n$	折纸：每加一个元素，可能性翻倍；42 折到月球	工具二
$\log_2 n$	猜数字：n 砍半几刀归 1；$2^{30}\approx$ 十亿 → 十亿只要 30 刀	工具三
$\log$ 不标底	换底 = 除以固定常数，被工具一丢掉	工具三
$n/2^k = 1 \Rightarrow k=\log_2 n$	”砍 k 刀剩 1”的方程化	工具三
$0+1+\cdots+(n-1)=\frac{n(n-1)}{2}$	握手问题 + 高斯首尾配对	工具四
$n!$	排队照相：位置逐个选，$n \times (n-1) \times \cdots \times 1$	工具五
$\log_2(n!)$	猜排列游戏：用是非题从 $n!$ 种队形锁定真相的最少提问数	工具三 + 五
$\log_2(n!) \approx n\log_2 n$	n 项相加、每项不超过 $\log_2 n$，量级就是 $n\log_2 n$	工具五
$T(n) = 2T(n/2)+n$	三句话的故事：劈两半各自搞定，合并再花 n	工具六
递归树”每层都是 n”	手算 T(8)=24 的竖式画成图：$\log_2 n$ 层 × 每层 n	工具六
特征方程 $x^2 = x+1$	猜等比 $T(n)=x^n$ → 代入 → 约分 → 解一元二次	工具六
$\varphi \approx 1.618$	斐波那契相邻项比值的极限，手算 89/55 可验	工具六

最后一句实话：这篇没有教任何原文之外的新知识——它只是把原文每个”一步跳过”的地方还原成三小步。如果重读原文时还有哪个符号卡住，那个符号就是下一篇陪读的题目。

参考来源

• 本篇是《别再背 Big-O：十大时间复杂度模式，其实是五种「工作量生成结构」》的配套陪读
• Big O Notation: Introduction — AlgoMaster.io（原速查图出处）
• Antti Laaksonen, Competitive Programmer’s Handbook 第 2 章（复杂度估算的竞赛视角）
• 文中所有数字均可手算复现：$2^{42}$ 折纸、$2^{10}=1024$、高斯配对 n=6、$T(8)=24$、斐波那契比值 89/55——算例本身就是验证