指数爆炸 — 「有限」和「人等得起」从这里分家
这一章讲三件事: 「每次翻一倍」到底有多快; 为什么「反正是有限的,让机器跑就行」这句话是错的; 以及碰上这种问题时,手上有哪几条路。
它在全书链条里的位置: 第 09 章的 32 个灯泡、第 11 章的 2ⁿ − 1、 第 12 章那串越长越快的数——它们其实是同一件事,这一章给它起名字、算清账。 第 14 章会把这件事反过来用,第 17 章会给出比它更硬的一条界。 需要的基础: 会乘法。
1. 先看现象:一张纸对折几次,能够到月球
一张 1 毫米厚的纸,假设它软 到可以无限对折。每对折一次,厚度翻一倍。 已知地球到月球大约 39 万公里,对折多少次能超过这个距离?1
先猜一个再往下看。 原书也让读者先猜:一百万次会不会太多?一万次差不多吧?2
全章的主走查:1 毫米的纸,要对折几次才够到月球
────────────────────────────────────────────────
§2 一次次翻倍,数着走 → 39 次
§4 同一件事在程序里的样子 → 30 个复选框,10.7 亿种
§5 于是那条界:「有限」不等于「做得完」
────────────────────────────────────────────────
图说:这一章的力气全在第 2 节那张表上 ——
它要做的不是算出 39,是让你亲眼看着它从毫米涨到公里。
2. 一次次翻倍:从 1 毫米到 39 万公里
这一节就是主走查,请顺着数字往下看3:
| 对折次数 | 厚度 | |
|---|---|---|
| 1 | 2 毫米 | |
| 10 | 1024 毫米 | 才 1 米零 2 厘米 |
| 20 | 1048.576 米 | 刚过 1 公里 |
| 30 | 1073.741 824 公里 | 超过 1000 公里了——东京到福冈的直线距离才 900 公里左右 |
| 35 | 34 359.738 368 公里 | |
| 39 | 549 755.813 888 公里 | 超过 39 万公里,到月球了 |
39 次。主走查走完了4。
这张表最该看的不是最后一行,是前 十行有多「不起眼」: 对折 10 次才 1 米出头,对折 20 次才刚过 1 公里。 可从 30 次到 39 次,只多了 9 次,厚度从 1073 公里涨到了 54 万公里——涨了 500 多倍。
画成图,这条曲线前面几乎贴着地面,后面几乎立了起来(原书的说法是「几乎垂直于横轴」)5。
3. 这件事的名字
这一节给上一节那个现象起名字。
这种「反复翻倍,数值急速涨起来」的情况,就叫指数爆炸6。 名字的来由很实在:折纸时厚度是 2 的多少次方,而那个「多少次方」正好是对折次数。
原书在这里挂了一条脚注,一句话就把边界划清了: 2ⁿ 会发生指数爆炸,而 n² 不会7。
n: 1 2 3 10 20 30
n²: 1 4 9 100 400 900 ← 涨得快,但涨得住
2ⁿ: 2 4 8 1024 104 万 10.7 亿 ← 这才叫爆炸
图说:n 在底下(n²)和 n 在上面(2ⁿ),是两个世界。
前十项还看不出差别,到 n = 30 就差了一百多万倍。
这一条要记住,因为它是第 14 章那条好消息的前提—— 同样是「跟规模有关」,涨法差一个数量级,结论就完全相反。
顺带认一下亲戚: 第 11 章汉诺塔的 2ⁿ − 1、第 09 章 32 个灯泡的 2³²、 第 12 章那串斐波那契数——全都是这一类。
4. 它藏在你的程序里:30 个复选框
这一节另起一处走查,把纸换成软件。
程序的设置界面上有一排复选框,每个都能勾或不勾8。 要把所有情况都测一遍,得测多少次?
用第 09 章的乘法法则:每个复选框 2 种状态,n 个就是 2ⁿ9:
| 复选框个数 | 要测多少次 |
|---|---|
| 5 个 | 2⁵ = 32 次 |
| 30 个 | 2³⁰ = 1 073 741 824 次(10.7 亿) |
30 个选项听起来一点都不多——随便打开一个稍微大点的应用的设置菜单就有这么多10。
接着原书把这 10.7 亿次换算成时间,这一步是这一章最狠的地方11:
假设一次测试要 1 分钟
一天能测 60 × 24 = 1440 次
一年能测 60 × 24 × 366 = 527 040 次
1 073 741 824 ÷ 527 040 ≈ 2037 年
两千多年12。这就是为什么软件开发里从来不做「一个不漏」的全覆盖测试, 而是挑那些可能互相影响的选项去测13。
5. 那条界:「有限」不等于「做得完」
这一节是全书最该记一辈子的一条,原书专门给它开了一小节。
很自然会有人这么想:虽说是指数爆炸,但它毕竟是有限的, 只要让计算机全速跑,总归会跑完的吧?
原书的回答是:这种想法是不正确的14。
理由只有一句:如果需要花上几千年才能解决,这种「解决」对人类没有意义。 一般的问题不仅要在「有限的时间」里解决,更要在人们期待的「短时间」内解决15。
以前你以为的两类问题: ┌ 有解 ┐ ┌ 无解 ┐
这一章之后: ┌ 有解,而且等得起 ┐
├ 有解,但要跑两千年 ┤ ← 新出现的一类
└ 无解 ┘
图说:中间那一类是这一章的产物。它「有限」、它「有答案」,
但它对人没有意义 —— 这条区分正是第 17 章讲不可解问题时的前提。
这条区分要记牢,因为第 17 章会在它上面再加一层: 那里的问题不是「跑得慢」,而是「根本写不出那个程序」。
6. 反过来用:密码就是靠它保护的
这一节另起第二处走查,展示同一件事的另一面。
现在的加密,是拿一串随机的 0 和 1 把消息搅乱,只有拿到同一串 0 和 1 的人才能还原16。 这串既用来搅乱、又用来还原的数,名字叫密钥。
密钥有多长,是按「位」数的:这里的「一位」就是一个 0 或者一个 1。 一个 6 位的密钥,就是排成一排的六个 0 或 1。
顺带认一个出门一定会撞见的名字:八位合起来叫作字节—— 一个字节就是排成一小串的八个 0 或 1,计算机存东西按它计量 (这一句是我们补的,书里只说「位」)。
假如不知道密钥,又想解开,最笨的办法是把所有可能的密钥一把一把试过去—— 这种一个不漏地试遍所有可能的做法,叫枚举17。
枚举用在破解密码上,还有个专门的名字:暴力破解。 「暴力」不是说手段凶狠,是说它不动脑子——不找规律,只靠试得够多。
那么密钥要多长才安全?数一数就知道18:
| 密钥长度 | 可能的密钥数 | 最多试几次 |
|---|---|---|
| 3 位 | 2³ | 8 次 |
| 4 位 | 2⁴ | 16 次 |
| 6 位 | 2⁶ | 64 次 |
| 512 位 | 2⁵¹² | 一个 155 位的数 |
每多 1 位,试解次数就翻倍——又是同一个指数爆炸19。
原书给了一个量感对照,值得原样记住: 假设宇宙里每一个基本粒子都是一台超级计算机, 从宇宙诞生开始不停地试,试到现在也试不完 512 位密钥的所有情况20。
所以那句「反正密钥个数是有限的,逐一试下来总会破解」—— 话不错,但不现实。「可以破解」和「可以在现实时间内破解」是两回事21。
7. 碰上它怎么办:先估空间,再挑一条路
这一节收尾,给出可操作的部分。
原书说,遇到难题的第一步是先理解这个问题的「空间」有多大22—— 就像在凌乱的房间里找一本书:先确认书确实在这个房间里, 再把范围缩到书架上,剩下的从头翻就行。
「有一套判断是否成功的办法」加上「有一套按顺序试的步骤」,就可以暴力破解—— 人工智能的先驱马文·明斯基把这条叫作「解迷原理」23。 但有些问题即使知道后面只需按顺序试,也照样解决不了——正是涉及指数爆炸的那些24。
原书列了四条路,并且每条都写明了代价25:
| 路 | 做法 | 代价 |
|---|---|---|
| 极力求解 | 换更快的机器、把活拆开让好多台同时算(这叫并行:同一批活分给几台机器一起干) | 问题规模稍微一大就顶不住;这是规模和机器性能之间的赛跑 |
| 变相求解 | 换个更聪明的解法,别一个不漏地试(第 07 章的涂色和七桥就是) | 不是每道题都找得到,这是极具难度的工作 |
| 近似求解 | 不求完全正确,求一个够用的近似答案 | 数学上不够严密,但实际够用 |
| 概率求解 | 用随机数去试,碰运气(这叫随机算法) | 说不准要多久,运气不好可能永远找不到 |
原书在「变相求解」那一栏后面还补了一句很沉的话: 更可悲的是,无论计算机如何进步,也总有解不了的问题26—— 这句话是第 15 到 17 章的引子。
8. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 对折 39 次到月球 | 给了完整的一张表,从 1 毫米数到 54 万公里 |
| 2ⁿ 爆炸而 n² 不爆炸 | 只用一条脚注给了这个结论,没有展开比较 |
| 30 个复选框要测两千年 | 给了完整换算(1 分钟 → 一年 52.7 万次 → 2037 年) |
| 「有限」不等于「做得完」 | 是作者专门开了一小节讲的主张,理由是「对人类没有意义」 |
| 宇宙里每个粒子都是超算也试不完 | 是作者的量感说明,书里没有给这个估算的过程 |
| 四种处理方法 | 给了四条 + 各自的代价,但没有给「什么时候选哪条」的判据 |
判断(我们的,不是书里的):这一章真正的用处是养成一个动作—— 动手之前先估一下「一共有多少种情况」。 很多性能事故的根子不在代码写得慢,在于那段代码要处理的组合数本身就是爆炸的 (每加一个筛选条件、每多一层嵌套循环、每多一个可选项)。 这个估算通常只要乘几个数,一分钟就能做完。 如果错,会错在: 真实系统里绝大多数组合根本不会出现, 按最坏情况估会吓着自己、做出过度设计。判据是: 那些组合是不是真的都会被走到。
这一章的边界:
- 没有给「多快才算爆炸」的正式说法(大 O 记号那一套原书刻意避开了, 我们在第 14 章补了两个名字并标明是书外的);
- 「解迷原理」只提了名字,没有给出处,也没有展开;
- 四条处理方法都只有一段介绍,没有具体做法;
- 没有讲「近似」和「概率」这两条路的真实例子;
- 密码那一节只讨论暴力破解,原书自己在脚注里说明了这一点。
9. 可带走的
- 1 毫米的纸对折 39 次就超过地月距离——不是几十万次,是 39 次;
- 前 20 次几乎看不出来(才 1 公里),后 9 次涨了 500 多倍——爆炸是后发的;
- 这件事叫指数爆炸:数值反复翻倍,而翻的次数就在 2 的右上角;
- 2ⁿ 会爆炸,n² 不会——同样跟规模有关,涨法差一个数量级,结论完全相反;
- 30 个复选框全测一遍是 10.7 亿种,一分钟测一次要跑 2037 年;
- 所以从来没有「一个不漏」的全覆盖测试,只能挑可能互相影响的去测;
- 「有限」不等于「做得完」:要跑两千年的解决方案,对人不算解决;
- 密码靠的正是它:每多 1 位钥匙数翻倍,512 位密钥连宇宙级的机器也试不完;
- 「可以破解」和「可以在现实时间内破解」是两回事;
- 碰上它先估问题空间,再从四条路里挑:堆机器、换解法、求近似、掷骰子—— 而其中「换解法」不是每次都找得到。
10. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 折纸问题 | 第7章 指数爆炸 | text/12-ch07.txt:32(搜「已知地球距月球约 390 000 km」) · :45(搜「先凭感觉估计一下」) |
| 那张翻倍表 | 第7章 指数爆炸 | text/12-ch07.txt:60(搜「10 → 1024 mm」) · :86(搜「30 → 1073.741 824 km」) · :99(搜「39 → 549 755.813 888 km」) · :101(搜「答案：39 次」) |
| 指数爆炸这个名字 | 第7章 指数爆炸 | text/12-ch07.txt:105(搜「我们把这种数值」) · :121(搜「而 n2 则不会」) |
| 30 个复选框 | 第7章 指数爆炸 | text/12-ch07.txt:146(搜「假设设定选项中有 5 个复选框」) · :166(搜「1 073 741 824」) · :179(搜「2037.3 年以上」) · :181(搜「不进行这种」) |
| 「有限」不等于「做得完」 | 第7章 指数爆炸 | text/12-ch07.txt:185(搜「不能认为是」) · :192(搜「这种「解决」就对人类没有意义了」) · :193(搜「更要在人们期待的「短时间」内解决」) |
| 密钥与暴力破解 | 第7章 指数爆炸 | text/12-ch07.txt:629(搜「随机字节流来加密」) · :649(搜「称为暴力破解法」) · :669(搜「每增加 1 位，试解次数就翻倍」) · :680(搜「假设构成宇宙的每一个基础粒子」) |
| 问题空间与解迷原理 | 第7章 指数爆炸 | text/12-ch07.txt:693(搜「理解问题描述的「空间」」) · :707(搜「解迷原理」) |
| 四种处理方法 | 第7章 指数爆炸 | text/12-ch07.txt:716(搜「极力求解」) · :722(搜「变相求解」) · :728(搜「无论计算机如何进步」) · :730(搜「近似求解」) · :734(搜「概率求解」) |