数据结构与算法 / 系统课时

代入法求解递推式

代入法求解递推式

得到递推式后,还需要证明它对应的渐进复杂度。代入法的核心不是机械展开,而是先猜测一个可能的界,再把猜测代回递推式,并用数学归纳法验证它在所有足够大的输入规模上成立。

学习目标

  • 根据递归结构猜测递推式解的数量级。
  • 使用归纳假设完成上界证明。
  • 识别证明失败时需要调整的常数或猜测形式。

代入法的证明结构

设定义域是 n=2kn=2^k,k 为非负整数。递推为 T(1)=1T(1)=1、T(n)=2T(n/2)+nT(n)=2T(n/2)+n。每层拆分的总非递归成本为 n,叶层也有 n 个单位成本,因此猜 T(n)=n(1+log⁡2n)T(n)=n(1+\log_2 n)。

代入法验证递推式上界的证明链路

用归纳验证猜测

当 n=1,等式给出 1,满足基例。若等式对 n/2 成立,代入得到 T(n)=2(n/2)(1+log⁡2(n/2))+n=n(1+log⁡2n)T(n)=2(n/2)(1+\log_2(n/2))+n=n(1+\log_2 n)。因此在该定义域上对每个 k 成立。

对 n≥2,有 log⁡2n≥1\log_2 n\ge1,所以 nlog⁡2n≤T(n)≤2nlog⁡2nn\log_2 n\le T(n)\le2n\log_2 n,得到紧确界。若直接用 cnlog⁡2ncn\log_2 n 覆盖基例 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。有限测试能检查等式实现,归纳证明负责未枚举的规模。

证明失败时如何修正

如果代回后多出一个无法消去的正项,不一定表示数量级猜错。先定位问题在基例还是归纳步骤。另看 S(1)=1S(1)=1、S(n)=2S(n/2)+1S(n)=2S(n/2)+1。只猜 S(n)≤cnS(n)\le cn 会在代入后留下 +1。加强为 S(n)≤cn−1S(n)\le cn-1,代入得 2(cn/2−1)+1=cn−12(cn/2-1)+1=cn-1,且 c=2 可覆盖基例。修正项要按原递推逐项检查。

另一个常见错误是只写“假设结论成立”,却没有说明归纳假设适用于哪些更小规模。强归纳形式应明确:对所有小于 nn 且满足定义域要求的规模,猜测都成立。

本课练习

  1. 使用代入法证明 T(n)=T(n/2)+1T(n)=T(n/2)+1 的上界为 O(log⁡n)O(\log n),写出归纳假设、代入过程和常数条件。
  2. 尝试证明 T(n)=2T(n/2)+n2T(n)=2T(n/2)+n^2 为 O(n2)O(n^2)。若直接猜测失败,调整常数或加强猜测,并说明修改原因。

本课总结

  • 代入法先猜测渐进界,再通过数学归纳法验证,而不是直接给出结论。
  • 证明成立的关键是正确代入归纳假设,并选择能覆盖递推步骤和边界条件的常数。
  • 数值实验可以辅助猜测,但不能替代对所有输入规模成立的证明。

下一课预告

下一课用递归树观察各层工作量和叶子边界,再判断哪种求解方法适合当前递推。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

代入法求解递推式

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通