形式陈述

代入法先猜测递推解的上界或下界，再用数学归纳证明。例如要证 $T(n)\le cn\log n$$T(n)\le cn\log n$，把归纳假设代入 $T(n)=2T(n/2)+n$$T(n)=2T(n/2)+n$，得到 $T(n)\le cn\log(n/2)+n=cn\log n+(1-c)n$$T(n)\le cn\log \left(n/2\right)+n=cn\log n+(1-c)n$，选择足够大的 $c$$c$ 并处理基例即可。常需加强猜测，如加入低阶修正项，以吸收取整和边界误差。

直觉

递推展开提供猜测，代入法负责“封口”：假设所有更小规模已经满足目标界，验证本层递推不会突破它。常数选择和加强命题是关键。

例子与边界

证明 $T(n)=T(\lfloor n/2\rfloor)+1=O(\log n)$$T(n)=T(\lfloor n/2\rfloor )+1=O(\log n)$ 时，可对所有小于 $n$$n$ 的规模做强归纳。直接猜 $T(n)\le cn$$T(n)\le cn$ 对某些递推虽真却过松，不能得到紧界；猜得过紧又可能因常数项失败。Big-O 证明只需对足够大 $n$$n$ 成立，但基例区间必须覆盖所有递归会落到的值。下界证明方向相反，不能把不等式符号机械照搬。

推论与应用

代入法是递推渐近界的通用严格证明技术，尤其适合主定理不适用、子问题规模不规则或需要精细常数修正的算法。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。