代入法

概述

代入法 是求解递归关系式的一种通用方法：先猜测解的界，再用数学归纳法严格证明。

定义

代入法

分两步进行：(1) 猜测递归关系式 $T(n)$ 的渐近界（上界或下界）；(2) 用数学归纳法验证猜测对所有 $n$ 成立。

核心性质

• 自上而下猜测：利用递归树或直觉直接提出一个猜测，然后用归纳法验证
• 自下而上收窄：先证明一个宽松的界，再逐步收紧。例如先证 $T(n)=O(n^3)$，再改进为 $O(n^2\lg n)$，最终精确到 $O(n^2)$
• 减去低阶项技巧：归纳假设中常需减去低阶项（如 $T(n)\le c{n}^2-bn$），以抵消递归展开时产生的额外常数项
• 适用范围广：不依赖递归的特定形式，比主定理更通用，但需要更多的数学技巧

章节扩展

第4章：代入法是第4章三种递归求解方法之一，与4.4 递归树法和主定理互补。递归树法常用于辅助猜测，代入法负责严格证明。

参见

• 4.3 代入法 — 代入法的详细步骤与示例
• 4.4 递归树法 — 常与代入法配合使用
• 数学归纳法 — 代入法的核心证明工具
• 主定理 — 另一种递归求解方法