笔记15-《程序员的数学》指数爆炸

2026.10.30 16:00 下午

指数爆炸
用 Ruby 验证
这一章的真正主题：对数

指数爆炸

折纸问题
- 1mm 的纸对折 n 次，厚度是 $2^n$ $2^{n}$ mm
  - 对折 1 次 → 2mm，2 次 → 4mm，依次翻倍
- 凭感觉估计：要折多少次能到月球？100 万次太多，1 万次差不多？
- 实际对应关系
  - 对折 10 次 → 1024mm = 1.024m
  - 对折 38 次 → 274877.906944km
  - 对折 39 次 → 549755.813888km
- 答案：39 次 —— 超过了地月距离（约 39 万公里）
- 仅仅反复「折纸」，数字不断翻倍，就很快得出非常庞大的数字
指数爆炸
- 这种数字急速增长的情况称为指数爆炸
- 之所以叫这个名字，是因为折纸时厚度（ $2^n$ ）的指数 n 就是对折次数
- 根据上下文，也可以称为「指数式增长」
- 图形上，指数函数迅速攀升，图像几乎垂直于 x 轴
- 对比第 6 章的汉诺塔： $2^n$ 会指数爆炸，而 n 不会
程序的设置选项
- 场景：某个选项组合会让程序崩溃，必须测试所有组合
- n 个复选框，每个 On/Off 两种状态，测试次数为 $2^n$ $2^{n}$
  - 这里使用了第 5 章的乘法法则
- 5 个复选框 → $2^5 = 32$ 次
- 30 个复选框 → $2^{30} = 1073741824$ 次（10 亿 7374 万 1824 次）
- 回顾：30 个选项说起来也不算多，打开稍大点的应用程序的「选项」菜单看看就知道
  - 但光测试全部可能性就需要 10 亿 7374 万 1824 次
  - 假设 1 次测试需要 1 分钟，1 天也只能测 $60 \times 24 = 1440$ 次
- 不能认为是「有限的」就不假思索 —— 有限不等于可行
寻找犯人的思考题
- 15 人中有 1 名罪犯，只问 3 次（问话对象可回答三种）能否找出
- 缩小规模：先假设犯人在 3 人中 → 向中间那个人提问即可确定
- 三种回答：「我是罪犯」/「罪犯在我左边」/「罪犯在我右边」
  - 中间的人不一定就是罪犯，但根据他的回答可以确定谁在
- 递归结构
  - 15 人 → 问正中间 → 筛出 7 人
  - 7 人 → 问正中间 → 筛出 3 人
  - 3 人 → 问正中间 → 锁定 1 人
  - 每问一次，范围减半 —— 这就是递归结构
二分法查找
- 二分法查找（binary search）：在有序数据中找出目标数据时「总是判断目标数据所在范围内正中间数据」的方法
- 条件：数据必须从小到大排列，且要查找的数必为其中之一
- 判断 1 次出现 3 种情况之一（兼顾完整性和网罗性）
  - 判断的数等于目标（查找成功）
  - 判断的数大于目标（目标在左边）
  - 判断的数小于目标（目标在右边）
- 和找犯人的方法完全一样
- 二分法查找使用了指数爆炸的方法
  - 判断 10 次 → 在 2047 个数据中找到目标
  - 判断 20 次 → 在 209 万 7151 个数据中找到目标
对数
- 乘方是「反复相乘到指定次数」，对数是「乘多少次能得到该数」
- 两者是互逆关系
  - $\log_{10} 100000 = 5$ ，因为 $10^5 = 100000$
  - $\log_{10} 1000 = 3$
- 指数法则与对数
  $\log_{10}(A \times B) = \log_{10} A + \log_{10} B \quad (A > 0, B > 0)$
- 乘法比加法难，用对数就能将乘法转换为加法 —— 即「将复杂计算转换为简单的计算」
- 三步法
  1. 分别求出 A 的对数和 B 的对数
  2. 把两个对数相加
  3. 相加结果进行乘方（对数的逆运算）
- 计算尺与对数刻度
  - 数轴刻度保持等间隔不变、各刻度上的数规定为乘方 → 加法转换为乘法
  - 另一种数轴刻度每向右移动 1 个单位数字只增加 1、刻度间隔递减，也是对数刻度
密码
- 加密用「密钥」的随机字节流，知道密钥的人才能解密
- 暴力破解法（brute-force attack）：加密算法没有弱点时，只能「一个不漏」地去试密钥
- 字长和安全性的关系
  - 3 位密钥 → 最多试 8 次（000、001、010、011、100、101、110、111）
  - 4 位密钥 → 16 种可能
  - 密钥字长越长，暴力破解越费时
如何处理指数爆炸
- 理解问题空间的大小
  - 问题空间越大，越难找到答案 —— 好比在凌乱房间里找书
  - 首先确认书确实在房间里吗 —— 要找的答案确实存在吗
  - 确定「在房间 A 或房间 B 中」后，A 中找不到就肯定在 B 中 → 这是逻辑思维
  - 知道书「在书架上」，寻找过程就变简单 → 缩小了要探索的问题空间
  - 书架中的书陈列有序 → 从头按顺序查找就能找到
    - 「从头开始按顺序查找」不难，困难的是如何达到「仅从头开始顺序查找」这一状态
  - 只要具备「判断是否已成功破解的方法」和「按顺序试解的步骤」，就可以使用暴力破解法
  - 人工智能先驱马文·明斯基（Marvin Minsky）将其命名为解迷原理
- 四种处理方法（本章只展开第一种）
  - 极力求解：增强计算机性能，超级计算机、并行计算机、更先进的计算机
    - 极力求解是重要的方法，但问题规模稍有扩大就应付不了
    - 这变成了问题规模和计算机性能之间的赛跑，必须意识到这点

用 Ruby 验证

def fold_mm(n)
  2**n
end

[10, 30, 38, 39].each do |n|
  km = fold_mm(n) / 1_000_000.0
  puts "对折#{n}次 = #{fold_mm(n)}mm = #{km.round(6)}km"
end

puts "5个复选框 = #{2**5} 次"
puts "30个复选框 = #{2**30} 次 = #{2**30}"
per_year = 60 * 24 * 366
puts "一年最多 #{per_year} 次测试"

def binary_search_steps(n)
  steps = 0
  while n > 1
    n = (n + 1) / 2
    steps += 1
  end
  steps
end
puts "2047个数据需判断 #{binary_search_steps(2047)} 次"
puts "2^21-1 = #{2**21 - 1}"

[3, 4, 8, 16, 32, 64, 128].each do |bits|
  puts "密钥 #{bits} 位 → 最多试 #{2**bits} 次"
end

puts "100亿人编号需要 #{Math.log2(10_000_000_000).ceil} 位"

输出：

对折10次 = 1024mm = 0.001024km
对折30次 = 1073741824mm = 1073.741824km
对折38次 = 274877906944mm = 274877.906944km
对折39次 = 549755813888mm = 549755.813888km
5个复选框 = 32 次
30个复选框 = 1073741824 次 = 1073741824
一年最多 527040 次测试
2047个数据需判断 11 次
2^21-1 = 2097151
密钥 3 位 → 最多试 8 次
密钥 4 位 → 最多试 16 次
密钥 8 位 → 最多试 256 次
密钥 16 位 → 最多试 65536 次
密钥 32 位 → 最多试 4294967296 次
密钥 64 位 → 最多试 18446744073709551616 次
密钥 128 位 → 最多试 340282366920938463463374607431768211456 次
100亿人编号需要 34 位

对折 39 次 = 549755.813888km 与书上完全一致； $2^{30} = 1073741824$ 也一致。

这一章的真正主题：对数

指数爆炸是症状，对数是解药。作者用折纸、选项测试、找犯人三件事把「 $2^n$ 增长有多可怕」演示到位，然后才引出对数 —— 因为对数正是把指数问题变回线性的那把钥匙。

三个层次值得分开看：

层次	内容	解决什么
认识问题	指数爆炸： $2^n$ 增长，30 次选项 = 10 亿次测试	知道规模
换个方向	二分法：判断 20 次 = 209 万数据；找犯人 3 次定位 15 人	用指数爆炸对付指数爆炸
换算单位	对数： $\log_{10}(A \times B) = \log_{10}A + \log_{10}B$	把乘法变加法

最反直觉的一层是第二个：指数爆炸既是问题也是武器。汉诺塔要 $2^n$ 次移动看起来是灾难，但同样的 $2^n$ 在二分查找里意味着 20 次判断覆盖 209 万个数据。区别只在于你是在「枚举」还是在「二分」。

而「解迷原理」那段的顺序值得记住 —— 作者把暴力破解的三个前提排成了递进：答案确实存在 → 缩小问题空间 → 让剩余空间有序可顺序搜索。他说「困难的是如何达到『仅从头开始顺序查找』这一状态」—— 这句话才是关键，第三步不是自动获得的。

至于最后的课后对话：世界人口 100 亿，编号需要 34 位，不是 300 位。因为 $2^{34} \approx 1.7 \times 10^{10} > 10^{10}$ 。而要给宇宙中所有原子编号，34 位也绰绰有余 —— 指数增长的另一面是它把极大的问题空间压缩成了极小的编号空间。

同一章里，对数既是把大数变小的工具，也是把乘法变加法的工具。这就是它为什么值得单独一节。

学习 :分类
指数爆炸 :标签