递归问题最容易掉队的点不是“会写公式”，而是“能解释为什么对”。 本节把证明分成两类：

• 归纳法：k=0,1,... 逐步成立；
• 调用树分析：把每层代价加总。

复杂度：从递推式到上界

大多数分治算法可写成：

T(n) = a * T(n / b) + f(n)

其中 a 是子问题个数，b 是缩小比例。

你可以直接用：

• 递归树：看每层总代价；
• 主定理：快速定位主项；
• 特判法：对低复杂度边界做数学归纳核验。

例如：

• T(n)=2T(n/2)+O(n) 通常是 O(n log n)；
• T(n)=2T(n/2)+O(1) 通常是 O(n)；
• T(n)=2T(n-1)+O(1) 是指数级风险，不适合直接大规模。

证明正确性的一般套路

1）正确性命题

把你要证明的目标写清楚： solve(problem) 返回的是该问题的正确解（或最优解）。

2）基准条件

在最小规模场景下直接返回正确值（如空区间、长度 1）。

3）归纳步

假设子问题求解正确，利用 combine 把子解构造成主问题答案；若任一环节不成立，整个函数就无法闭合。

THM递归正确性的核心等价

“每次将子问题解正确，并且合并函数保持数学意义正确”，是递归正确性的充分条件之一。

易错点

• 把“复杂度减半”误写成“复杂度减一”；
• combine 漏了排序/边界导致返回错位；
• 主定理使用前忘记判断规模是否能整除，或遗漏非标准规模处理。

本章算法复杂度对照

问题	典型递推或结构	时间复杂度	额外空间
汉诺塔	T(n)=2T(n-1)+Θ(1)	Θ(2^n)	O(n) 栈
记忆化爬楼梯	每个状态只完整计算一次	O(n)	O(n)
递归折半查找	T(n)=T(n/2)+Θ(1)	O(log n)	O(log n) 栈
快速幂	T(n)=T(n/2)+Θ(1)	O(log n)	O(log n) 栈
归并排序、逆序对	T(n)=2T(n/2)+Θ(n)	O(n log n)	O(n)
快速排序	取决于划分均衡程度	平均 O(n log n)，最坏 O(n²)	平均 O(log n) 栈
快速选择	只进入目标一侧	平均 O(n)，最坏 O(n²)	平均 O(log n) 栈
合并 K 个链表	按 K 二分，节点参与 O(log K) 层合并	O(N log K)	O(log K) 分治栈，另有链表递归栈
表达式所有结果	输出规模可能指数增长	与不同括号结果规模相关	记忆化结果集合

WARN大 O 不能脱离输入形态

快速排序和快速选择的复杂度不能只写一个固定结论。必须说明枢轴划分是否均衡，以及讨论的是平均情况还是最坏情况。

一道短练习

设 f(n)=f(floor(n/2))+f(ceil(n/2))+n。 1）写复杂度；2）给一个直观解释：为什么“每层代价都在 n 量级”。