每日科普 · 2026-10-20 周二
考研 408 × 求职面试
知识点 · 算法设计与分析 · 进阶
递归方程求解：代入法、递归树法与主定理
递归方程描述分治算法的时间代价，典型形式为 T(n)=aT(n/b)+f(n)。常用三招：
1. 代入法：先猜一个渐近界，再用数学归纳法代入验证；关键是把低阶项和常数吸收掉，有时需猜更紧的界。
2. 递归树法：把递归展开成树，算每层总代价，再对所有层求和；叶子代价和与根代价的较量能帮助发现答案。
3. 主定理：对 T(n)=aT(n/b)+f(n)，a≥1、b>1，比较 f(n) 与 n^{log_b a}。f 多项式小时，T=Θ(n^{log_b a})；同阶时，T=Θ(n^{log_b a} log n)；f 多项式大且满足正则条件时，T=Θ(f(n))。核心口诀是“比较叶子和根，相等多乘 log”。注意主定理不是万能的，非标准递归、非多项式差异等需用代入法或递归树。
每日一题 · 算法设计与分析
递归方程求解：代入法、递归树法与主定理
求解递推式 T(n)=2T(n/2)+n^2 的渐近复杂度（n>1）：
A. Θ(n log n)
B. Θ(n^2)
C. Θ(n^2 log n)
D. Θ(n^3)
解析
a=2，b=2，则 n^{log_b a}=n。f(n)=n^2 与 n 相比是多项式更大（差一个 n），且 f(n)=n^2 满足正则条件，所以落入主定理第三类，T(n)=Θ(f(n))=Θ(n^2)。选 B。易错点是看到递归树每层和递减就直接猜 n^2 log n，只有同阶才多乘 log。
面试小贴士 · 算法设计与分析
递归方程求解：代入法、递归树法与主定理
面试常给递推式问复杂度或问主定理分支。答题先写 a、b、f(n)，算 n^{log_b a}，再比较 f 的阶，并说明用哪类。不会证明就用递归树解释。易错：忽略正则条件、同阶与多项式更大混淆、硬套非标准递归。
代码实现 · C
代码示例
#include <stdio.h>
#include <math.h>
int main() {
// 示例：T(n)=2T(n/2)+n^2
double a=2, b=2, d=2;
double p=log(a)/log(b); // n^{log_b a} 的指数
printf("log_b(a)=%.2f\n", p);
if (d < p - 1e-9) {
printf("情形1: Theta(n^%.2f)\n", p);
} else if (fabs(d-p) <= 1e-9) {
printf("情形2: Theta(n^%.2f log n)\n", p);
} else {
// f(n)=n^d 且 d>p 时，第三类成立
printf("情形3: Theta(n^%.2f)\n", d);
}
return 0;
}