数据结构与算法 / 系统课时
代入法求解递推式
代入法求解递推式
得到递推式后,还需要证明它对应的渐进复杂度。代入法的核心不是机械展开,而是先猜测一个可能的界,再把猜测代回递推式,并用数学归纳法验证它在所有足够大的输入规模上成立。
学习目标
- 根据递归结构猜测递推式解的数量级。
- 使用归纳假设完成上界证明。
- 识别证明失败时需要调整的常数或猜测形式。
代入法的证明结构
设定义域是 ,k 为非负整数。递推为 、。每层拆分的总非递归成本为 n,叶层也有 n 个单位成本,因此猜 。

用归纳验证猜测
当 n=1,等式给出 1,满足基例。若等式对 n/2 成立,代入得到 。因此在该定义域上对每个 k 成立。
对 n≥2,有 ,所以 ,得到紧确界。若直接用 覆盖基例 n=1,右侧总是 0,增大 c 也无效。对任意正整数规模,必须先明确取整或证明比较关系,不能直接套用这条精确等式。
用程序检查猜测
下面的程序验证小规模结果,并拒绝递推定义域之外的输入。对 n=1 不计算除以 log 的比值。
python
def recurrence(n):
if type(n) is not int or n < 1 or n & (n - 1):
raise ValueError("n 必须是正整数且为 2 的幂")
if n == 1:
return 1
return 2 * recurrence(n // 2) + n
for n in (1, 2, 4, 8, 16, 32):
k = n.bit_length() - 1
value = recurrence(n)
assert value == n * (k + 1)
print(f"n={n}, T(n)={value}")输出的 T(n) 依次为 1、4、12、32、80、192。有限测试能检查等式实现,归纳证明负责未枚举的规模。
证明失败时如何修正
如果代回后多出一个无法消去的正项,不一定表示数量级猜错。先定位问题在基例还是归纳步骤。另看 、。只猜 会在代入后留下 +1。加强为 ,代入得 ,且 c=2 可覆盖基例。修正项要按原递推逐项检查。
另一个常见错误是只写“假设结论成立”,却没有说明归纳假设适用于哪些更小规模。强归纳形式应明确:对所有小于 且满足定义域要求的规模,猜测都成立。
本课练习
- 使用代入法证明 的上界为 ,写出归纳假设、代入过程和常数条件。
- 尝试证明 为 。若直接猜测失败,调整常数或加强猜测,并说明修改原因。
本课总结
- 代入法先猜测渐进界,再通过数学归纳法验证,而不是直接给出结论。
- 证明成立的关键是正确代入归纳假设,并选择能覆盖递推步骤和边界条件的常数。
- 数值实验可以辅助猜测,但不能替代对所有输入规模成立的证明。
下一课预告
下一课用递归树观察各层工作量和叶子边界,再判断哪种求解方法适合当前递推。
按自己的节奏,确认真正理解。