计算机数学入门（二）：世界是连续的，机器是离散的

上一篇：（一）计算机里的数，不是数学里的数——讲的是一个数怎么被压进机器。 这一篇：讲一堆东西怎么被压进机器，以及压完之后冒出来的那些结构。

耗时：读完约 50 分钟，动手约 2 小时。

开头：一个 15 kHz 的声音，听起来像 1 kHz

先做个实验。有一个 15000 赫兹的正弦波——这是人耳能听到的、偏高的音。用不同的采样率去"录"它，再反推它的频率：

这个现象有个专门的名字：混叠（aliasing）。

而且它有个可怕的属性：你听不出来错了。 出来的还是一个光滑的、干净的正弦波，听起来完全正常，只是频率不对。没有任何噪声、没有杂音、没有失真感。它变成了一个合法的、但错误的信号。

这就是"离散化"这件事最典型的代价：不是变差，是变成另一个东西，而且不报警。

上一篇讲的是一个数怎么被压进机器。这一篇讲的是世界怎么被压进机器——时间、声音、图像、关系、结构，全都是连续的或者巨大的，机器只能装离散的、有限的。

这一篇要回答一个问题：这一刀砍下去，代价是什么，怎么算？

一、第一刀：采样——把连续的时间切成时刻

采样定理：一句话说清

要无失真地记录一个频率为 f 的信号，采样率必须大于 2f。

这个 2f 叫奈奎斯特频率。所以：

• 人耳上限约 20000 Hz → 需要采样率 > 40000 Hz → 这就是 CD 用 44100 Hz 的原因
• 电话只传 300–3400 Hz → 采样率 8000 Hz 就够 → 这就是为什么电话里的声音"闷"

混叠的公式：错了多少，能算出来

如果采样率不够，高频信号会被"折"到低频上去。折到哪？这个公式能精确算：

f_观测 = |f_真实 − k × f_采样|
其中 k 取使结果最接近 [0, f_采样/2] 的整数

验证一下上面那张表（实测 vs 公式）：

五位全中。 这不是巧合，这是数学在起作用。

为什么这件事值得一个成年人认真看

因为它教了一件事：离散化不是"近似"，是"映射"。

近似是"我尽量接近你"。映射是"我把你换成另一个东西，这个换法有确定的规律"。

混叠的规律是确定的，所以：

• 你可以提前算出来会不会发生（fs > 2f 吗？）
• 你可以提前防（采样前先加一个低通滤波器，把高于 fs/2 的部分砍掉）
• 但如果没做，事后救不回来（15000 Hz 和 1000 Hz 采出来的样本，一模一样，谁也不知道原来是哪个）

一个信息如果没被采到，它就永远消失了，而且不告诉你它走了。

这是"离散"这件事的第一条铁律，后面所有的坑都是它的变体。

二、第二刀：量化——把连续的数值切成档位

采样解决了"什么时候取"，量化解决"取到多准"。

8 位和 16 位差多少

把 [-1, 1] 的信号切成分档，实测误差：

每多 1 位，信噪比涨 6.02 dB。 这个数字你可以自己背下来用——它叫"量化噪声公式"，音频、图像、传感器、ADC 选型全都用这一条。

8 位是 256 档，16 位是 65536 档。位数每加 1，档数翻倍，而信噪比只涨 6 dB。 这是典型的对数关系——跟上一篇的"有效位数"是同一个东西的两种说法。

量化的坑：它跟舍入一样，会积累

上一篇讲过 round() 有好几套定义。量化就是舍入的物理版本：

• 截断（往下取）：系统性偏低，误差均值不为零，累加会漂
• 四舍五入：误差均值接近零，但每次最大差半档
• 抖抖（dither）：故意加一点随机噪声再量化，把系统性误差变成随机误差——这是音频工业的标准做法

最后这一条特别反直觉：为了更准，故意加噪声。 因为系统性偏差会被人耳听成"失真"，随机噪声听着像"底噪"，而人耳对底噪的容忍度高得多。

这件事说明：误差有两种，“偏"和"散”。偏比散可怕。 这也是为什么上一篇里金融系统用"银行家舍入"——它在统计上不偏。

三、第三刀：有限——把无限多的可能压进有限的格子

切完时间和数值，还有一刀更根本的：机器的状态是有限的。

鸽巢原理：一句话，一个后果

n 个鸽子放进 m 个笼子，n > m 时，至少有一个笼子里有两只鸽子。

听起来是废话。但它的一个推论，直接判了"无损压缩"的死刑：

如果有 n 个文件，而你能用的更短表示只有 n−1 种，那么至少有一个文件压完就还原不回来。

实测验证——把 1 字节的全部 256 种可能、2 字节的全部 65536 种可能都拿 zlib 最高压缩级别压一遍：

一个都没压小。

原因很简单：随机数据没有规律，zlib 找不到可压缩的东西，反而要加上格式头，所以变大了。而鸽巢原理保证了：任何压缩算法，都不可能在所有文件上都变小。 只要有文件变小，就必然有文件变大。

这就是为什么：

• 你压一个 .zip 再压一次，文件不会更小
• “无限压缩"的软件一定是骗局
• 加密后的数据是不可压缩的（它已经接近随机）

这一条把"机器能做什么"划出了一条硬边界：不是算力不够，是数学上不可能。 这跟上一篇的"整数会绕圈"是同一类结论——不是 bug，是结构。

四、三刀砍完，剩下的东西叫"结构”

到这儿，我们已经把连续的世界砍成了：有限个时刻、有限个档位、有限个状态。

那么问题来了：砍完剩下的这堆东西，有什么规律可研究？

这就是离散数学要回答的问题。它不研究"连续变化"，它研究"一堆离散的东西之间怎么关联"。

四样东西，构成它的主体。而这四样，恰好就是你写代码时天天在用的四种容器：

下面一样一样来，每一样都给实测数字。

五、集合：为什么"查一下在不在"有三种代价

这是最基础的问题：给我一个 ID，它在这个集合里吗？

三种做法，实测同一个任务——100 万个 ID，查 10 万次：

（线性扫描那一行是实测 100 次外推的——真跑 10 万次要七个多小时，我没等。）

三者差了一百万倍。 同样的答案，同样的结果（命中都是 92 个），代价差六个数量级。

这三种代价背后的数学

不是"哈希快、扫描慢"这么模糊的东西。它们各自对应离散数学里的一个结构：

1. 集合本身 = 无序、不重复 判断"在不在"的最小代价，理论上限是 O(1)——这需要"直接算地址"，也就是哈希函数。

2. 有序 = 全序关系 排序之后，你获得了一个额外结构：全序（任意两个元素都能比大小）。这个额外结构让你能做二分，代价降到 O(log n)。 代价是：维护这个序要花钱。 插入一个新元素，有序数组要挪位置，哈希表不用。

3. 无序且无索引 = 只能一个个看 这就是 O(n)。大多数"程序慢"，本质是这一条——你手上有一堆东西，但没有任何结构，所以只能扫。

记住这句话：数据结构不是"存东西的容器"，是"用空间和预处理换取操作代价的契约"。 选数据结构，本质是选"你要为哪种操作付钱"。

一个真实的对撞：去重，哈希还是排序

实测 200 万条数据、重复率 75.5%：

结果完全一致，哈希快 3.7 倍。

但这不是"哈希永远赢"。如果数据本来就近乎有序、或者你同时还需要排序结果，那排序去重更划算——它一次干了两件事。这是工程判断，不是数学结论。

数学只告诉你代价的形状，告不告诉你选哪个。

六、关系：等价、偏序、全序——三把不同的尺子

“关系"这个词在离散数学里是严格的：从集合 A 到集合 B 的一个子集。人话就是"谁和谁有关系”。

其中三种最重要，因为编程里所有的"比较"都是它们：

1. 等价关系（Equivalence）——“算同一个”

三个条件：自反、对称、传递。

• == 判相等就是它
• 去重依赖它
• 数据库的 GROUP BY 依赖它

它最重要的性质：把集合切成互不相交的块。 每一块内部全算"同一个"，块之间全算"不同"。

这一条有个直接应用：并查集（Union-Find）。判断"A 和 B 是不是同一伙的"，本质是在等价关系上做查询。社交网络找共同好友、编译器判断两个变量是否别名、图像分割连通区域——全是它。

坑：等价关系一旦不满足传递性，去重就会漏。上一篇的"浮点比较不传递"就是这个——a == b、b == c 但 a != c，你的去重逻辑会留下本该合并的东西。

2. 偏序（Partial Order）——“谁必须在谁前面”

三个条件：自反、反对称、传递。关键在"偏"：不是任意两个都能比。

• 任务依赖：A 必须在 B 之前，但 C 和 D 谁先都行
• 包依赖：web 依赖 auth，auth 依赖 db……

这一条的直接应用是拓扑排序。 实测一个五节点的依赖图：

web    → auth, db, log
auth   → db, crypto
db     → log
crypto → log
log    → （无）

拓扑排序结果：

log → db → crypto → auth → web

注意 db 和 crypto 的相对位置不唯一——这就是"偏"的意思：它不给你唯一答案，它只保证不违反约束。

加一条边制造环（log → crypto），排序立刻返回失败：

有环 → None

这就是"依赖循环"检测的原理。 你见过 npm 报 circular dependency，见过 Docker build 卡住，见过 CI 无限等待——底下都是这一件事：偏序关系里出现了环，序就不存在了。

“排不出顺序"不是工具的问题，是数学上不存在这个顺序。

3. 全序（Total Order）——“谁大谁小，永远能比”

在偏序基础上再加一条：任意两个都能比。

• 数字的大小
• 字符串的字典序
• 时间的先后

排序算法全都依赖它。而排序算法的正确性，依赖比较函数真的满足全序。

实测一个经典 bug——用 int(a - b) 当比较函数（这是很多人的"优化”）：

sorted([0.1, 0.2, 0.3, 0.7, 1.1, 0.5], key=cmp_to_key(lambda a,b: int(a-b)))
# 结果: [0.1, 0.2, 0.3, 0.7, 1.1, 0.5]

结果跟没排一样。 因为 0.1 − 0.2 = −0.1，int(−0.1) = 0，意思是"相等"。所有差值绝对值小于 1 的都被判成相等，于是整个序列原封不动。

而且它不报错。排序算法拿到一个不一致的比较器，结果是未定义的——可能乱序、可能崩、可能时对时错。

一个不满足全序的比较函数，不是一个"不太准"的排序，是一个"没有意义"的排序。

七、图：为什么"关系"要用图画

集合只回答"在不在"。关系回答"谁跟谁有关"。而如果关系能串起来，你就得到了图。

图是离散数学里最"有用"的一块，因为现实世界的关系几乎都是图：

• 网页链接 → 搜索排名
• 好友关系 → 推荐
• 网络拓扑 → 路由
• 包依赖 → 构建顺序
• 状态转移 → 编译器优化

一个反直觉的实测：社交网络的"六度"

随机生成 5 万个节点、平均每个节点连 10 条边的图，从任意点做 BFS：

可达节点：49,997 / 50,000
平均跳数：4.92
耗时：179 ms

平均只要 5 跳，就能摸到几乎整个网络。 这就是"六度分隔"的数学基础——不是玄学，是随机图的直径是 O(log n)。

注意这是随机图。真实社交网络有更强的局部聚集，跳数会比随机图多，但依然是对数级的。“世界很小"这件事，是图论的一个定理，不是一句感慨。

最短路径的代价

同样六个邻居的随机图，跑 Dijkstra：

节点数涨 20 倍，耗时涨 28 倍——接近线性。为什么？因为边也是线性增长的（每个点固定 6 条边）。如果图更密（边随 n² 增长），代价就会变成 O(n² log n)。

这一段在告诉你：复杂度不是一个抽象公式，它取决于"你的数据长什么形状”。 同一个算法，稀疏图上是线性的，稠密图上就不是。这就是为什么第五层（复杂度）要单独讲。

八、计数：为什么"看起来不多"的选择会爆炸

最后一样，也是最容易低估的：计数。

2ⁿ：开关组合

2⁶⁴ 是多少？ 在每秒 10 亿次运算的机器上，穷举一遍要：

1.845×10¹⁹ ÷ 10⁹ = 1.845×10¹⁰ 秒 ≈ 584.5 年

584 年。 这就是为什么 64 位密码"够用"——不是它不可破，是破它的时间超过一切实际意义。

n!：比指数更疯

20 个元素的排列有 2.4×10¹⁸ 种。

这就是为什么"旅行商问题"（TSP）在 20 个城市时暴力还能算，30 个城市就彻底不行——30! ≈ 2.65×10³²，比 2⁶⁴ 还大 13 个数量级。

这一条是"算法设计"存在的全部理由。 如果暴力能算，就不需要聪明算法。正是因为状态空间是指数级的，才需要"动态规划"“分支限界"“近似算法"这些人类智力的产物。

排列 vs 组合：差多少

同样从 10 个里挑：

挑 5 个：组合 252 种，排列 30240 种——差 120 倍。

为什么？因为组合不管顺序，排列管。“要不要管顺序"这一个问题，能把解空间扩大一百倍。 写代码时：“这个循环要不要嵌套"“要不要排序后再比较”——本质都是在回答这个问题。

九、一个交叉口：生日悖论（通向概率的门）

离散结构讲完了。但有一件事必须在这里说，因为它是离散和概率的交界处，而且是所有人都会算错的地方。

23 个人里，有两个人生日相同的概率是多少？

直觉：365 天才 23 个人，大概 6%？实际是 50.7%。

公式：p ≈ 1 − e^(−n²/2N)。要 50% 概率，n ≈ 1.177√N = 22.5 人。实测一致。

这不是统计学的花招，它是计数的直接后果：你要比的是所有配对，不是"某个人和某个人”。

23 个人有 C(23,2) = 253 对。253 次机会撞 365 个格子——当然比 23 次机会大得多。

它在工程里长什么样

哈希碰撞。一个 32 位哈希有多少种值？2³² ≈ 42.9 亿——听起来很多。

但按生日悖论，只要约 7.7 万条记录，就有 50% 概率撞上。

实测（每次 5 轮取平均）：

七万条就开始撞，二十万条撞五次。

这就是为什么：

• 数据库的 32 位自增 ID 不够用来做"唯一随机标识”
• 文件名用 32 位哈希会撞
• 密码必须加盐——不加盐，攻击者用一张彩虹表就能批量破
• MD5 已经不安全——它只有 128 位，且已被构造碰撞

不同位数的哈希，撞车所需记录数：

“空间很大"和"不会撞"是两件事。 这是离散数学给你的最重要的一条工程直觉。

十、回到体系：这一篇在八层里是哪一层

上一篇给了八层目录，这一篇是第二层：离散结构。它的位置是这样的：

一句总结这一篇

离散化不是"近似”，是三种映射： 采样把时间映射成时刻（可混叠），量化把数值映射成档位（有噪声），有限把可能映射成格子（会撞）。 三种映射各有确定的规律，所以三种都能提前算、提前防、也为时已晚。

而三刀砍完之后剩下的东西，不是残渣，是结构——集合、关系、图、计数。这四样才是计算机真正生活在里面的世界。

十一、动手：六个实验

全部能自己跑。数字你自己跑出来可能差一点，但量级和结论会一致。

实验 1：亲耳听到混叠（Python，不用装东西）

import math

def 采样(f, fs, 秒=1.0):
    return [math.sin(2*math.pi*f*i/fs) for i in range(int(fs*秒))]

def 估频率(x, fs):
    过零 = [i for i in range(1, len(x))
            if (x[i-1] < 0 <= x[i]) or (x[i-1] > 0 >= x[i])]
    if len(过零) < 2: return 0
    return (len(过零)-1)/2 / ((过零[-1]-过零[0])/fs)

for fs in [44100, 22050, 16000, 11025, 8000]:
    x = 采样(15000, fs)
    print(f"采样率 {fs:6d} → 听到 {估频率(x, fs):8.1f} Hz")

跑出来会看到 15000 / 7050 / 1000 / 3975 / 1000。亲手看到"15000 变成 1000”，比读十遍公式管用。

实验 2：量化误差和 6.02n+1.76

import math
for bits in [4, 8, 12, 16, 24]:
    levels = 2**bits
    sq = 0; n = 100000; maxerr = 0
    for i in range(n):
        x = math.sin(2*math.pi*i/n*100)
        q = round((x+1)/2*(levels-1))/(levels-1)*2-1
        e = abs(q-x); sq += e*e; maxerr = max(maxerr, e)
    rms = math.sqrt(sq/n)
    print(f"{bits:2d}bit 最大误差 {maxerr:.2e}  SNR {20*math.log10(0.7071/rms):6.2f} dB "
          f"（公式 {6.02*bits+1.76:.2f}）")

实验 3：证明压缩不可能压缩所有文件

import zlib
小 = 0
for v in range(256):                      # 全部 256 种单字节
    if len(zlib.compress(bytes([v]), 9)) < 1:
        小 += 1
print(f"256 种单字节，压小的有 {小} 个")   # 0

想再狠一点，把 range(256) 换成 range(65536) 加 to_bytes(2,'big')。还是 0。

实验 4：三种查找，差一百万倍

import random, bisect, time
random.seed(3)
ids = set(random.randrange(10**9) for _ in range(1000000))
tests = [random.randrange(10**9) for _ in range(100000)]

t = time.time(); sum(1 for x in tests if x in ids)
print(f"哈希: {(time.time()-t)*1000:.1f} ms")

arr = sorted(ids)
t = time.time()
for x in tests:
    i = bisect.bisect_left(arr, x)
print(f"二分: {(time.time()-t)*1000:.1f} ms")

# 线性那一行别真跑 10 万次，跑 100 次乘 1000

实验 5：拓扑排序和环检测

from collections import deque

def 拓扑排序(g):
    入度 = {n: 0 for n in g}
    for n, ds in g.items():
        for d in ds: 入度[n] += 1
    q = deque([n for n in g if 入度[n] == 0]); out = []
    while q:
        n = q.popleft(); out.append(n)
        for m, ds in g.items():
            if n in ds:
                入度[m] -= 1
                if 入度[m] == 0: q.append(m)
    return out if len(out) == len(g) else None       # None = 有环

deps = {"web": ["auth","db","log"], "auth": ["db","crypto"],
        "db": ["log"], "crypto": ["log"], "log": []}
print("正常:", 拓扑排序(deps))
deps2 = dict(deps); deps2["log"] = ["crypto"]        # 加一条环
print("有环:", 拓扑排序(deps2))                       # None

自己把那条环加进去，看它变成 None。 这就是你 CI 卡住时发生的事。

实验 6：生日悖论撞给你看

import random
random.seed(1)
for n in [1000, 10000, 65536, 200000]:
    总撞 = 0
    for trial in range(5):
        s = set(); c = 0
        for i in range(n):
            h = hash(f"{trial}-{i}") & 0xFFFFFFFF
            if h in s: c += 1
            s.add(h)
        总撞 += c
    print(f"{n:7d} 条 → 实测撞 {总撞/5:.1f} 次  理论 {n*(n-1)/2/2**32:.1f}")

十二、带走的东西

一句话：

离散化就是把连续的世界换成"时刻 + 档位 + 格子”，每一步都有确定的误差规律——所以每一步都能算，也都能防。

三句话：

1. 采样错误是"换了个东西"，不是"变差了" —— 混叠出来的信号完全合法、完全干净、完全错误，而且事后无法还原。信息没被采到就彻底消失。
2. 数据结构是"用空间换操作代价"的契约 —— 同一件事，三种做法差一百万倍。选错不是慢一点，是七个多小时。
3. “空间大"不等于"不会撞” —— 32 位空间 43 亿，七万条就有一半概率撞。这是离散数学给你最值钱的一条工程直觉。

下一篇

（三）怎么保证对：从"我觉得没问题"到"我证明它没问题"

从一个真实的死循环开始，讲清楚循环不变量是什么、为什么它能证明程序对、归纳法为什么是它的原型。然后是命题逻辑、量词、德摩根律——为什么"条件写反了"是一个数学错误，不是手滑。

深水区

• 离散数学主干：Rosen《Discrete Mathematics and Its Applications》。集合、关系、图、计数、逻辑全在里面，是标准教材。
• 轻一点的入口：MIT 6.042（Mathematics for Computer Science）公开课资料，免费，讲得更像人话。
• 信号这条支线：Oppenheim《Signals and Systems》前几章讲采样定理，是所有数字信号处理的起点。
• 图论单独看：Diestel《Graph Theory》是研究生级别；入门用 Rosen 的图论那几章就够。

这些书我不做页码引用——不同版本页码不同，写了就是骗你。按书名和章节找。

附：本篇所有数字的来源

全部在本机跑出来：Ubuntu / Python 3.8 / gcc 9.4 / x86-64。不是引用别人的。

• 混叠：15000 Hz 信号在 44100/22050/16000/11025/8000 采样率下实测 15000 / 7050 / 1000 / 3975.1 / 1000 Hz
• 量化信噪比：4/8/12/16/24 bit 实测 25.68 / 49.97 / 74.07 / 97.85 / 146.34 dB（公式 6.02n+1.76）
• 压缩：1 字节 256 种、2 字节 65536 种，zlib 最高级别压小 0 个
• 三种查找（100 万 ID、10 万次查询）：哈希 26.2 ms、二分 378.1 ms、线性约 28060 秒
• 去重（200 万条、75.5% 重复）：哈希 336 ms、排序去重 1258 ms，结果均 490,987 个
• 拓扑排序：五节点依赖图排序出 log→db→crypto→auth→web；加一条环后返回 None
• Dijkstra：1000/5000/20000 节点 3.7 / 19.9 / 105.8 ms
• BFS：5 万节点、平均度 10 的随机图，平均 4.92 跳，179 ms
• 生日碰撞（32 位）：1000/10000/65536/100000/200000 条实测 0.0/0.0/0.6/1.6/4.8 次
• 组合：C(10,5)=252 vs P(10,5)=30240；20! = 2,432,902,008,176,640,000
• 2⁶⁴ 次操作 @10⁹/s = 584.5 年

你自己机器上跑出来的数字会略有不同（CPU、Python 版本、编译优化）。差一点不影响结论——结论是结构性的。