推荐系统里有一个算方案数的函数,早期写法是教科书上的斐波那契递归:fib(n) = fib(n-1) + fib(n-2)。n=30 时接口还能很快返回;n=40 时网关五秒超时;n=45 时进程 CPU 打满,请求再也没回来。没有异常,没有死锁,就是算不完。
同一周,另一个同事说归并排序「比 O(n log n) 慢得多」。代码逻辑没问题,但每一层都在用切片复制数组,十万条数据复制了几百万个元素。复杂度没估错,代价被漏掉了。
两个现象指向同一件事:递归函数的开销不能靠数循环估。得先把「规模为 n 的问题花多少时间」写成一个关于更小规模的等式,再解这个等式。这个等式叫递推式,解它的工具是递归树、主定理和数学归纳法。这篇从递推式怎么写开始。
现象:n 只加了 5,调用次数涨了 11 倍
先给朴素递归加一个计数器,把「算得慢」变成可比较的数字。
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
for n in (35, 40):
calls = 0
fib(n)
print("n=%d calls=%d" % (n, calls))
真实输出:
n=35 calls=29860703
n=40 calls=331160281
规模只加了 5,调用次数从 2986 万涨到 3.3 亿,约 11 倍。每加 5 乘 11,等价于每加 1 乘 1.62,也就是黄金比例 φ。继续按这个倍数外推,45 大概要 36.7 亿次调用。单机 Python 不可能在超时前算完,原因不在机器慢,而在于同一批子问题被重复计算了指数次。
这种计数器的写法值得记住:它只统计函数被调用了多少次,不测时间。时间受机器负载、解释器版本、CPU 频率影响,同一段代码跑两次可能差一倍;调用次数是确定的,换台机器也一样。判断「算法本身是否重复计算」时,计数比计时可靠。
把调用次数和 n 的关系写成式子:C(n) = C(n-1) + C(n-2) + 1,基准 C(0) = C(1) = 1。它和斐波那契同阶,解出来是 φ 的 n 次方。这就是递推式的价值:不用真跑,就能知道增长的量级,也知道为什么 n 只挪了一点,结果就崩了。
递推式:把递归的代价写成方程
递推式(recurrence)把 T(n) 写成「若干个子问题的代价 + 当层自己的工作量」。它有三个要素:子问题有几个、每个多大、把结果合并起来要多少。二分查找是 T(n) = T(n/2) + O(1);归并排序是 T(n) = 2T(n/2) + O(n);快排最坏是 T(n) = T(n-1) + O(n)。
写式子前必须先定义 n 是什么:数组长度、节点个数,还是输入位数。定义不同,式子完全不同。第二个坑是漏掉当层代价:归并的合并、快排的划分、二分的一次比较,都是实打实的工作量,写成 0 就会把结果估小一阶。
还要写清基准情况。T(1) = O(1) 是递归出口,没有它,递推式没有起点。工程代码里的空输入、单元素分支可以合并成 O(1),但要确认它们确实是常数,而不是又藏着一层循环。
递推式本身不是答案,它是一张待解的方程。同一个 T(n) = 2T(n/2) + n 解出来是 n log n,把当层换成 n² 就变成 n²。下面三种工具,就是解这类方程的三把螺丝刀。
举个具体的:归并排序把长度 n 的数组分成两个 n/2,各自排好后再合并。合并要逐元素比较,代价与 n 成正比,所以写成 2T(n/2) + cn。这里的 c 是每次比较和搬移的常数,写成 O(n) 时被吞掉了。估量级可以吞,算实际耗时不能吞。
数学归纳法:为什么两步能覆盖所有自然数
数学归纳法用来证明「对所有自然数 n,命题 P(n) 成立」。它只有两步:基础步,验证 n=1 成立;归纳步,假设 P(k) 成立,推出 P(k+1) 也成立。两步合起来,1 成立推出 2 成立,2 成立推出 3 成立,一直推下去。
这个「一直推下去」有严格依据,叫良序原理:自然数的任意非空子集都有最小值。假设存在反例,取最小的那个 n。它不可能是基础步覆盖的 1,所以 n-1 满足 P;由归纳步,n 也满足 P,矛盾。因此不存在反例。
例子:证明 1 + 2 + ... + n = n(n+1)/2。基础步 n=1,左边 1,右边 1×2/2=1。归纳步假设前 k 项的和是 k(k+1)/2,那么前 k+1 项是 k(k+1)/2 + (k+1) = (k+1)(k+2)/2,正好是公式把 n 换成 k+1 的样子。
再换一个例子:高度为 h 的满二叉树有多少个节点。基础步 h=0,只有根,1 个,等于 2 的 1 次方减 1。归纳步假设高度 h 时有 2^(h+1)-1 个节点,再往下挂一层 2^(h+1) 个叶子,总数是 2^(h+1)-1 + 2^(h+1) = 2^(h+2)-1,正好是高度 h+1 的公式。关键在于「接上一层」这个动作,它把结构的变化翻译成了数字的变化。
归纳法证明的是所有 n,但代码只能验证有限个。下面把 n 从 1 到 100 全算一遍:
print(all(sum(range(1, n + 1)) == n * (n + 1) // 2
for n in range(1, 101)))
True
返回 True 只说明前 100 个没问题,不能替代归纳步。反过来,归纳步写错时,有限验证也经常能过,因为错误往往在更大的 n 才暴露。归纳法和递推式是配套的:递推式给出 T(n) 与更小规模的关系,归纳法用来验证「猜出来的解」对所有 n 成立。
递归树:每层代价乘层数
递归树把递推式展开成一棵树:每个节点写它的当层代价,子节点写子问题。总代价等于所有节点代价之和。决定结果的是三个量:每层总代价、层数、叶子数量。
模板一,二分查找。T(n) = T(n/2) + O(1)。每层只有一个子问题,当层代价是常数,层数就是把 n 除以 2 直到 1 的次数,也就是 log₂n。总和 O(log n)。实测最坏步数:
def bs_steps(n):
lo, hi, steps = 0, n - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
hi = mid - 1
return steps
for n in (1000, 1000000, 1000000000):
print(n, bs_steps(n))
1000 9
1000000 19
1000000000 29
n 从一千涨到十亿,规模乘了一百万,步数只从 9 涨到 29。这就是对数的形状:底数不改变量级,只改变常数。
模板二,归并排序。T(n) = 2T(n/2) + O(n)。第 k 层有 2 的 k 次方个节点,但每层总代价始终是 n:第一层合并 n 个,第二层两个 n/2,加起来还是 n。层数是 log₂n,总和 n log n。实测 n=1024:
ms_calls = 0
copied = 0
def merge_sort(a):
global ms_calls, copied
ms_calls += 1
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
copied += len(a)
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
data = list(range(1024, 0, -1))
res = merge_sort(data)
print("递归调用:", ms_calls)
print("拷贝元素:", copied)
print("正确:", res[0] == 1 and res[-1] == 1024)
递归调用: 2047
拷贝元素: 10240
正确: True
递归调用 2047 次,正好是 2n-1,也就是满二叉树的节点数;拷贝元素 10240 次,正好是 n 乘 log₂n(1024×10)。这个数字就是「每层 n、共 10 层」的直接证据。真实代码里如果多写一次切片,它还会涨。
模板三,快排最坏。T(n) = T(n-1) + O(n)。每次只去掉一个元素,树退化成一条链,层数是 n,每层代价从 n 递减到 1,总和 n(n+1)/2,量级 n²。实测:
def qs_worst(n):
if n <= 0:
return 0
return n + qs_worst(n - 1)
print(qs_worst(900))
print(2000 * 2001 // 2)
405450
2001000
900 时总代价 405450,和 900×901/2 对得上;2000 时按同一公式是 2001000,涨了约 4.9 倍。规模翻十倍,代价就接近一百倍,这就是平方级。
三个模板的读法一致:先数每层代价,再数层数,最后相乘。难点在「每层代价是否恒定」:归并恒定,快排递减,二分查找是常数。写不出每层代价,说明递推式还没写对。
递归树不需要画全。真正要数的是三件事:每层有多少节点、每个节点的代价加起来是多少、一共有多少层。前两层通常就够看出规律,剩下的是用归纳法证明这个规律对第 k 层也成立。画满整棵树既画不下,也没必要。
主定理:比较三个量,而不是背公式
主定理处理标准形式 T(n) = aT(n/b) + f(n)。a 是子问题个数,b 是规模缩小的倍数,f(n) 是当层代价。它不需要背三行公式,只要比较两个量:子问题规模总量的增长速度 n^log_b(a),和当层代价 f(n)。
如果 f(n) 明显小于 n^log_b(a),当层很便宜,总代价由叶子决定,结果是 Θ(n^log_b(a));如果两者同阶,每层代价和叶子增长一样快,要多乘一个 log n;如果 f(n) 明显更大,当层工作压倒了子问题,结果是 Θ(f(n)),但还要满足一个正则条件。
import math
for a, b, fe in ((2, 2, 1), (8, 2, 2), (2, 2, 2), (2, 4, 2)):
p = math.log(a, b)
tag = "同阶" if fe == p else ("当层更大" if fe > p else "子问题更大")
print("a=%d b=%d f=n^%d 临界=n^%.2f %s" % (a, b, fe, p, tag))
a=2 b=2 f=n^1 临界=n^1.00 同阶
a=8 b=2 f=n^2 临界=n^3.00 子问题更大
a=2 b=2 f=n^2 临界=n^1.00 当层更大
a=2 b=4 f=n^2 临界=n^0.50 当层更大
第一组是归并排序,同阶,结果是 n log n。第二组 a=8、b=2,临界 n³,子问题增长更快,结果是 n³。第三组当层 n² 更大,结果是 n²。第四组 b=4 让临界降到 n 的 0.5 次方,当层 n² 仍然更大,结果还是 n²。
不适用的情形要记牢:b 等于 1,规模根本没缩小,比如 T(n)=T(n-1)+n;子问题规模不相等,比如 T(n)=T(n/3)+T(2n/3)+n;f(n) 不是多项式,或者 a 随层变化。这些情况主定理给不出结论,得回到递归树或者直接展开。
正则条件那句话不是摆设。它要求 f(n) 的增长不能太怪,比如 f(n) 本身已经是指数级、比子问题总量还大得多时,结论会退化。工程里遇到的 f(n) 基本是 n 的多项式乘对数,通常满足;写作业时如果 f(n) 是 2 的 n 次方,就要停下来想一想。
三种工具怎么选
递归树最直观,适合第一次推导和讲给别人听,能看见「每层多少、几层」;缺点是 n 很大时画不出来,只能画前两层再猜规律。主定理最快,套三个量就能出结果,适合标准形式;缺点是它不解释原因,也不适用于变形。
直接展开适合一眼能看出规律的式子,比如 T(n)=T(n-1)+1 直接就是 n,T(n)=T(n-1)+n 直接就是 n²。工程排查里的顺序通常是:先写递推式,画两层树确认当层代价,再看是否落进主定理;落不进就继续展开,或者换变量把式子化标准。
不要一上来背结论。结论对不上时,你没法判断是模型写错了还是公式记错了,而这两种错误的修法完全不同。
记忆化:把指数级压回线性
斐波那契递归慢,是因为 fib(n-1) 和 fib(n-2) 会重复计算同一批子问题,递归树里有大量完全相同的节点。记忆化把算过的结果按参数存起来,下一次直接取。
memo = {}
mcalls = 0
def fibm(n):
global mcalls
mcalls += 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fibm(n - 1) + fibm(n - 2)
return memo[n]
for n in (20, 25, 30):
memo = {0: 0, 1: 1}
mcalls = 0
print("n=%d value=%d calls=%d" % (n, fibm(n), mcalls))
真实输出:
n=20 value=6765 calls=39
n=25 value=75025 calls=49
n=30 value=832040 calls=59
朴素版在同样的 n 上是 21891、242785、2692537 次调用,记忆化版是 39、49、59。59 正好是 2n-1:每个 n 从 2 到 30 各算一次,加上对 0 和 1 的两次访问。n=40 时朴素版 331160281 次,记忆化版 79 次,差了六个数量级。
代价是空间:缓存要存 n 个结果,递归深度还是 n。记忆化只改变调用次数,不改变单次调用的成本,也不改变递归深度。
它也不是万能的。状态必须是「参数到结果」的纯函数映射;参数里带可变对象、时间、随机数,缓存就会返回错误结果。缓存键写错更隐蔽:用列表当键会直接报错,转成字符串又可能因为格式不同而永远不命中,表现为「加了缓存但一点没快」。
举个真实会踩的坑:缓存键写成 str(args),而 args 里有一个字典,字典的打印顺序在不同版本或不同构造方式下会变,同一个逻辑参数得到两个键。命中率看起来是零,代码里却明明写了缓存。修法是把参数规范化成固定顺序的元组,而不是依赖对象的默认字符串形式。
一张现象对照表
下面这些现象,基本都能在递推式、递归树或计数器的某一步找到原因。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 递归函数 n=40 超时,n=45 不可用 | 同一子问题被重复计算,调用次数按指数增长 | 加调用计数器,看 n 每加 1 或 5 的倍数 |
| 归并排序实测比理论慢很多 | 每层切片和合并都在拷贝,常数因子很大 | 统计每层拷贝的元素数,而不是只看比较次数 |
| 估成 O(n log n),实测像 O(n²) | 递推式写错,子问题规模没有真的减半 | 打印每层子问题的长度,确认是否按 b 缩小 |
| 递归几千层就栈溢出 | 递归深度等于 n,超过了语言默认上限 | 查递归上限,并统计实际最大递归深度 |
| 加了缓存,速度没有变化 | 缓存键不一致,或者每次参数都是新对象 | 打印缓存条目数和命中次数,看命中率 |
| 主定理算出的阶和实测对不上 | 递推式不满足标准形式,子问题规模不相等 | 展开两层递归树,核对 a、b、f(n) |
| 摊还复杂度被当成平均情况 | 总代价均摊到每次,但单次仍可能很贵 | 找最坏的那一次,单独测它的耗时或计数 |
| 大 O 相同,线上却慢一个档 | 常数、内存访问、拷贝没有被渐近分析计入 | 用计数器统计实际操作次数,再乘单次成本 |
边界与代价
第一,大 O 会忽略常数,而常数可能致命。归并排序的 n log n 里,拷贝占了很大一块;同样是 O(n log n),原地归并和每层切片的实际耗时能差几倍。渐近分析回答「规模变大时怎么涨」,不回答「这台机器上要几秒」。
第二,递归深度有限制。Python 默认上限是 1000 层,qs_worst(1000) 在 900 时还能算出 405450,到 1000 就直接抛 RecursionError。线性递归在数学上没问题,在运行时先撞墙。深递归要么改迭代,要么显式加栈,要么放大上限并承担内存风险。
第三,摊还不等于平均。摊还分析说的是「一串操作的总代价除以操作次数」,允许某一次特别贵;平均情况是对输入分布取期望,两者不是一回事。用摊还结论去承诺单次延迟,会在最坏的那一次翻车。
摊还的典型例子是动态数组扩容:每次扩容搬 n 个元素很贵,但扩容间隔越来越长,把总搬移量除以插入次数,得到常数。这不代表每次插入都便宜,某一次插入照样会卡住几百毫秒。对外承诺 P99 延迟时,摊还数字没有意义。
第四,主定理只适用于特定形式。子问题规模必须统一按 b 缩小、f(n) 要满足正则条件、a 和 b 是常数。快速排序的平均情形、斐波那契递归、带两个不同规模子问题的算法,都不在主定理的标准形式里。
第五,记忆化有空间成本。缓存 n 个状态就要 n 份内存,状态是二维的还会变成 n²。缓存无上限时,长时间运行的服务可能被它撑爆,需要配合淘汰策略。
第六,渐近分析在 n 很小时会失效。n=10 时,O(n²) 的算法完全可能比 O(n log n) 的快,因为后者的常数和递归开销更大。选择算法时,先看数据规模,再看量级。
小结与练习
这篇的主线可以压成三句。递推式是估递归复杂度的唯一入口,写清子问题个数、缩小倍数和当层代价;递归树把式子展开成「每层代价乘层数」,主定理是比较三个量的快捷方式;归纳法负责证明猜出来的解对所有 n 成立,记忆化则用空间把重复子问题压成一份。
还有一句提醒:复杂度是地图,不是路况。先用递推式看量级,再用计数器核对常数,两件事都做完,才敢说「这个函数能扛住多大的 n」。
下一篇讲鸽巢原理与计数。这一篇一直在算「有多少工作」,下一篇回答「为什么一定有重复」:n 个物品放进 m 个盒子,只要 n 大于 m,至少一个盒子有两个。缓存冲突、哈希碰撞、抽屉问题,都是它的应用。
当天可以自己验证的练习:
- 用计数器跑朴素斐波那契的 n=20、25、30,验证调用次数是 2F(n+1)-1;再跑记忆化版本,验证是 2n-1。
- 对
T(n)=2T(n/2)+n手画 n=8 的递归树,逐层求和,再用代码统计实际节点代价,两个结果对照。 - 把归并排序的切片改成索引范围原地归并,统计拷贝元素数的变化,并解释常数因子为什么会影响实测。
- 用归纳法证明
1+3+...+(2n-1)=n²,再写代码验证前 100 项,说明有限验证和证明的区别。 - 判断
T(n)=T(n-1)+T(n-2)+1是否适用主定理,若不适用,用递归树或特征方程说明它的量级。