把算法讲给别人听
本节目标：能对一个算法讲清正确性、复杂度与被淘汰的数据规模。
讲不清就是没懂
这门课一开始定的目标是「能做出来」。到这一课要升一级：能讲明白。
这两件事差的不是表达能力，是理解的深度。有两句话听起来很像，其实完全不同：
- 「我记得 0/1 背包的循环要逆着写。」
- 「逆着写的时候，
dp[j - wt]读到的是还没考虑当前物品时的答案，所以当前物品最多只能用一次。」
第一句在第 26 课那种「照葫芦画瓢」的场合够用，换一道题就不够了——因为你不知道那条规则是为哪个目的服务的，也就不知道什么时候可以违反它。
这一课给一套可自查的讲解结构，然后拿它去拷问你自己学过的每个算法。凡是讲不下来的地方，就是还有一层没吃透。
三分钟讲解稿的四段
一份能自查的讲解稿，固定分成四段。顺序不能换，因为后一段要用到前一段的结论。
第一段：这个东西在解决什么问题。 一句话，不许出现算法名字和代码。比如「并查集在解决：一堆元素分成若干组，我要快速知道两个元素在不在同一组」。
第二段：为什么它是正确的。 这是最难也最关键的一段。不许复述代码流程——「先这样再那样然后返回」是流程，不是论证。要讲的是不变式：每一步结束时，什么东西一定成立；以及为什么这个不变式能推出最终答案。
第三段：复杂度怎么推出来的。 不许只报结论。O(n \log n) 要能说清楚那个 \log n 是从哪一步来的——是每层分一半（分治），还是每次操作让某个量减半（堆的上浮）。
第四段：多大的规模会把它淘汰掉。 这是最常被跳过的一段，也是最能看出你懂没懂的一段。任何算法都有它不适用的输入，说不出失效条件的，等于不知道它的边界在哪。
下面三节分别把第二、三、四段拿出来，各量一组数据给你看。
讲得出为什么，才写得出对的
先看最直接的一种检验方式：如果你说不清「为什么」，那你多半也写不出对的。
0/1 背包的内层循环要逆序，这是第 25 课的内容。正序写会怎样？
W = 10
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
def knap(direction, w):
"""direction='back' 是 0/1 背包，'forward' 是完全背包。"""
dp = [0] * (w + 1)
for wt, val in items:
js = range(w, wt - 1, -1) if direction == 'back' else range(wt, w + 1)
for j in js:
dp[j] = max(dp[j], dp[j - wt] + val)
return dp[w]
print(f' 物品（重量, 价值）= {items}，背包容量 {W}')
print(f' 内层循环逆序（0/1 背包）: {knap("back", W)} 分')
print(f' 内层循环正序（完全背包）: {knap("forward", W)} 分')
print()
print(' 逆序时每一轮 dp（容量 0..10）：')
dp = [0] * (W + 1)
for wt, val in items:
for j in range(W, wt - 1, -1):
dp[j] = max(dp[j], dp[j - wt] + val)
print(f' 处理完（{wt}, {val}）: {dp}')
print(' 正序时每一轮 dp（容量 0..10）：')
dp = [0] * (W + 1)
for wt, val in items:
for j in range(wt, W + 1):
dp[j] = max(dp[j], dp[j - wt] + val)
print(f' 处理完（{wt}, {val}）: {dp}') 物品（重量, 价值）= [(2, 3), (3, 4), (4, 5), (5, 6)]，背包容量 10
内层循环逆序（0/1 背包）: 13 分
内层循环正序（完全背包）: 15 分
逆序时每一轮 dp（容量 0..10）：
处理完（2, 3）: [0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3]
处理完（3, 4）: [0, 0, 3, 4, 4, 7, 7, 7, 7, 7, 7]
处理完（4, 5）: [0, 0, 3, 4, 5, 7, 8, 9, 9, 12, 12]
处理完（5, 6）: [0, 0, 3, 4, 5, 7, 8, 9, 10, 12, 13]
正序时每一轮 dp（容量 0..10）：
处理完（2, 3）: [0, 0, 3, 3, 6, 6, 9, 9, 12, 12, 15]
处理完（3, 4）: [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]
处理完（4, 5）: [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]
处理完（5, 6）: [0, 0, 3, 4, 6, 7, 9, 10, 12, 13, 15]两种写法循环体一字不差，只有 range 的方向不同，答案差了 2 分。 而且注意一个细节：
正序处理完第一件物品 (2, 3) 时，dp[10] 已经是 15 了——15 = 3 × 5，意思是这件重量为 2 的物品被用了 5 次。可题目说每件物品只有一件。这就是那个 bug 的全部：正序时 dp[j - wt] 读到的已经被这一轮更新过了，所以当前物品被重复使用。
反过来，逆序处理完 (2, 3) 时 dp[10] = 3，只用了一次——因为 dp[j - wt] 读到的还是「上一轮」的值。
这就是第二段该讲的东西。 它比「要逆序」这句话长，但它能回答一个「要逆序」回答不了的问题：如果我确实想要完全背包（物品能用无限次），该怎么写？ ——把方向倒过来。
复杂度要推，不能背
第三段的要求是「推出来」，不是「报结论」。看并查集，这是最容易被一句「查得很快」糊过去的结构。
第 19 课讲过并查集。它的查询代价有一个微妙之处：不同的实现方式，总代价差三个数量级。
def uf(n, mode):
"""n-1 次合并 + n 次查询，返回（总步数, 单次查询最坏步数）。
合并时一律 parent[find(i-1)] = i，也就是每次都把「已经建好的那棵树」
挂到新结点下面 —— 这样不管什么模式，合并后 parent 都是一条长度 n 的链。
四种模式的区别只在「查询时做不做路径压缩」和「合并时看不看秩」。
"""
parent = list(range(n))
rank = [0] * n
total = 0
worst = 0
def find(x):
nonlocal total, worst
root, d = x, 0
while parent[root] != root:
root = parent[root]
d += 1
total += d
if d > worst:
worst = d
if mode in ('compress', 'both'):
while parent[x] != root:
parent[x], x = root, parent[x]
return root
for i in range(1, n):
if mode in ('rank', 'both'):
a, b = find(0), find(i)
if a != b:
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
else:
parent[find(i - 1)] = i
for i in range(n):
find(i)
return total, worst
N = 2000
print(f' n = {N}：{N - 1} 次合并 + {N} 次查询，数「沿 parent 走了多少步」')
print(' 做法 总步数 平均每次 单次最坏')
for mode, name in (('chain', '不压缩、不按秩'),
('compress', '只用路径压缩'),
('rank', '只按秩合并'),
('both', '按秩合并 + 路径压缩')):
t, w = uf(N, mode)
print(f' {name:<26} {t:>9,} {t / N:>7.2f} {w:>7,}')
print(f' n(n-1)/2 = {N * (N - 1) // 2:,}') n = 2000：1999 次合并 + 2000 次查询，数「沿 parent 走了多少步」
做法 总步数 平均每次 单次最坏
不压缩、不按秩 1,999,000 999.50 1,999
只用路径压缩 3,997 2.00 1,999
只按秩合并 1,999 1.00 1
按秩合并 + 路径压缩 1,999 1.00 1
n(n-1)/2 = 1,999,000「不压缩、不按秩」那一行的总步数是 1,999,000，正好等于 n(n-1)/2。 这个数字不是巧合——它就是把一条长度 n 的链从每个结点各走一遍的总和，也就是 O(n^2)。能说出「这个数字为什么正好是 n(n-1)/2」，就说明你真的推出来了，而不是背了个结论。
「摊还」是什么意思
上面那张表最值得盯的是第三行：只用路径压缩，总步数 3,997，但单次最坏仍然是 1,999。
这两个数放在一起会让人困惑：到底快不快？答案是两个都对——它说的是两件不同的事：
- 总代价很小：3,997 步，比不压缩的 1,999,000 步小了 500 倍。
- 单次可能很慢：第一次查询那条长链时，它老老实实走了 1,999 步才把路径压平。
「摊还」就是把这两件事分开说的术语：不是「每一次都快」，而是「总代价小」——某一次特别慢的账，由它顺手压平路径、让后面所有查询都变快这笔收入抵掉了。
所以「并查集查询是 O(\alpha(n))」这句话的准确含义是摊还 O(\alpha(n))，不是每一次都 O(\alpha(n))。面试或讲题时把「摊还」两个字说清楚，和不说的差别很大。
我这张表里的「只按秩合并」和「按秩合并 + 路径压缩」总步数完全一样（都是 1,999）。这不是我写错了，而是这个合并顺序恰好让按秩合并单独用就够了：每次合并都是「大树 + 一个孤立点」，按秩规则会自然把孤立点挂到树下，深度停在 1，路径压缩无事可做。
换一种合并顺序，两者就分开了。 下一节量给你看。
def uf_tournament(n, compress):
"""先合相邻两块、再合相邻两大块（像淘汰赛）。返回（总步数, 单次最坏）。"""
parent = list(range(n))
rank = [0] * n
total = 0
worst = 0
def find(x):
nonlocal total, worst
root, d = x, 0
while parent[root] != root:
root = parent[root]
d += 1
total += d
if d > worst:
worst = d
if compress:
while parent[x] != root:
parent[x], x = root, parent[x]
return root
step = 1
while step < n:
i = 0
while i + step < n:
a, b = find(i), find(i + step)
if a != b:
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
i += 2 * step
step *= 2
for i in range(n):
find(i)
return total, worst
for N in (2000, 4000):
print(f' n = {N}')
for compress, name in ((False, '只按秩合并'), (True, '按秩合并 + 路径压缩')):
t, w = uf_tournament(N, compress)
print(f' {name:<24} 总步数 {t:>9,} 平均每次 {t / N:>6.2f} 单次最坏 {w:>5,}')
print(f' n × log2(n) = {N * (N.bit_length() - 1):,}') n = 2000
只按秩合并 总步数 10,864 平均每次 5.43 单次最坏 10
按秩合并 + 路径压缩 总步数 3,987 平均每次 1.99 单次最坏 2
n × log2(n) = 20,000
n = 4000
只按秩合并 总步数 23,728 平均每次 5.93 单次最坏 11
按秩合并 + 路径压缩 总步数 7,986 平均每次 2.00 单次最坏 2
n × log2(n) = 44,000这张表要横着看，看「规模翻倍时总步数翻了几倍」：
- 只按秩合并：10,864 → 23,728，是 2.18 倍。规模翻倍而代价涨了 2.18 倍，比线性多一点——这正是 n \log n 的样子。
- 两者都用：3,987 → 7,986，是 2.00 倍。规模翻倍代价正好翻倍——这就是线性，也才配得上「摊还 O(\alpha(n)) 近似常数」这个说法。
这就是第三段该讲的东西。 说「并查集接近 O(1)」是背结论；能指出「规模翻倍时总步数只翻一倍」是推导；能进一步说清「因为路径压缩把长链摊平了，代价被后面的查询分掉」才是真懂。
顺带一个反过来的结论：这张表也说明了只按秩合并不是没用——它在上一节的合并顺序下已经足够好，在这一节也只是 O(n \log n)。路径压缩的收益取决于合并顺序可不可控。讲清「什么时候可以省掉路径压缩」，比背「两个优化都要写」有用。
适用的边界在哪
第四段是「多大的规模会把它淘汰掉」。这一段的关键在于任何算法都有不适用的输入，而且失效条件通常不在平均情况上，在某个特定的输入形状上。
看快排。它最常被讲成「平均 O(n \log n)，很快」，但这句里藏了一个前提：主元挑得够随机。取首元素当主元，遇到已经排好序的输入会怎样：
import random
def qsort_count(a):
"""朴素快排，取首元素当主元，返回比较次数。"""
if len(a) <= 1:
return 0
p = a[0]
lo = [x for x in a[1:] if x < p]
hi = [x for x in a[1:] if x >= p]
return len(a) - 1 + qsort_count(lo) + qsort_count(hi)
n = 300
rng = random.Random(5)
rand_data = list(range(n))
rng.shuffle(rand_data)
print(f' 取首元素当主元的快排，n = {n}：')
print(f' 随机数据 : {qsort_count(list(rand_data)):>8,} 次比较')
print(f' 已经排好序 : {qsort_count(list(range(n))):>8,} 次比较')
print(f' 完全逆序 : {qsort_count(list(range(n, 0, -1))):>8,} 次比较')
print(f' n(n-1)/2 = {n * (n - 1) // 2:,}') 取首元素当主元的快排，n = 300：
随机数据 : 3,298 次比较
已经排好序 : 44,850 次比较
完全逆序 : 44,850 次比较
n(n-1)/2 = 44,850同一份代码、同一个 n，随机数据 3,298 次比较，已经排好序 44,850 次——差 13.6 倍。 而且 44,850 正好是 n(n-1)/2，也就是退化成了 O(n^2)。
为什么会这样：主元取首元素，而已经排好序的数组里首元素正好是最小值。于是每次划分都得到「空 + 剩下的全部」，递归深度变成 n，每次只消掉一个元素。
注意这有多危险：快速排序「平均 O(n \log n)」这句话没有错，但如果你只讲这一句，听的人会以为它在所有输入上都安全。一个只讲平均情况的讲解，等于没讲边界。
第四段该讲的东西长这样：「朴素快排平均 O(n \log n)，但如果主元取首元素、且输入已经有序或逆序，会退化成 O(n^2)，n = 300 时比较次数从 3,298 涨到 44,850。修法是随机选主元或三数取中。」
这段话里「n = 300 时 3,298 对 44,850」就是最有说服力的部分——具体数字比「会退化」三个字有分量得多，因为它能让人估出多大规模会出事。这正是第四段要回答的问题。
把术语翻译成直觉
最后一段是贯穿全程的要求：能用日常语言说一遍。
术语是压缩过的信息，它省了字，但也藏了理解。「摊还」「不变式」「宽松上界」这些词，能背下来不代表能用。检验方法是把它翻译回具体的动作和数字：
| 术语 | 翻译成直觉 |
|---|---|
| 摊还 O(\alpha(n)) | 某一次查询可能走 1,999 步，但它顺手把整条路径压平了，后面几百次查询都只走 1 步 |
| 不变式 | 每做完一步，这两个堆的长度差不超过一——不是某一步成立，是每一步都成立 |
| 退化成 O(n^2) | 主元每次都取到最小值，划分变成「空 + 其余」，n = 300 时要比较 44,850 次 |
| 近似常数 | 规模翻倍时总步数只翻一倍（3,987 → 7,986） |
| 上界是紧的 | 不是「不超过这个数」，是真的能取到这个数（1,999,000 恰好等于 n(n-1)/2） |
这张表的用法：讲到一个术语时，强迫自己往右列说一遍。说得出来说明懂了，说不出来就是还在背。
这一课用到的判断
- 讲不清就是没懂。 「记得要逆序」和「说出逆序时
dp[j-wt]读的是上一轮的值」是两种深度，后者才能回答「那我想要完全背包该怎么办」。 - 第二段讲不变式，不背流程。 复述代码顺序是流程；说清「每步之后什么一定成立、为什么能推出答案」才是论证。
- 第三段要推，不报结论。 能指出「1,999,000 正好是 n(n-1)/2」是推导；说「并查集很快」是背结论。
- 摊还是「总代价小」，不是「每次都快」。 只用路径压缩总步数 3,997（比不压缩小 500 倍），但单次最坏仍是 1,999 步。这两个数同时成立。
- 看增长率比看单点更快。 规模翻倍时总步数翻 2.18 倍是 n \log n，翻 2.00 倍是线性——这张表比任何一句「接近 O(1)」都有说服力。
- 路径压缩的收益取决于合并顺序可不可控。 我实测的一种合并顺序下，只按秩合并已经足够（1,999 步），两者都用毫无增益；换成锦标赛式合并才分开（10,864 对 3,987）。
- 每个算法都有失效条件，而且失效通常挂在某个特定输入形状上。 快排平均 O(n \log n) 没错，但主元取首元素遇上有序输入会退化——n = 300 时 3,298 变 44,850。
- 第四段要带数字。 「会退化」没人能估出风险，「n = 300 时 44,850 次」能让人立刻知道多大规模会出事。
- 术语要能翻译回直觉。 说不出来就是在背。
这一课是概念课，动手部分不配 lab，落在纸面上。挑五个你已经学过的算法，照下面的结构各写一份讲解稿，然后讲出来。
- 先列五个算法。 建议从这些里挑，它们的「为什么」都不好讲：并查集、0/1 背包、区间 DP、二分答案、堆求前 k 大。至少挑一个你觉得自己「会用但讲不清」的。
- 每份稿子照四段写。 一段一段来，不许跳过任何一段：
- 它在解决什么问题（一句话，不许出现算法名字和代码）
- 为什么它是正确的（讲不变式，不许复述代码流程）
- 复杂度怎么推出来的（O(\cdot) 里每一项是从哪一步来的）
- 多大的规模会把它淘汰掉（必须带一个具体数字）
- 讲一遍，最好录音。 讲给自己听也算。不要照着稿子念——念稿子不会暴露你没懂的地方。讲完记下被问住或卡壳的位置，那些就是还没吃透的地方。
- 把术语翻译一遍。 每份稿子里至少挑一个术语（如「摊还」「不变式」「宽松上界」），用日常语言说一遍，并带上一个具体数字。
- 回头补洞。 卡住的地方回到对应课件重看那一节，然后只重写那一段，不用整篇重来。