算法设计第 2 章：递归与分治——三步套路与 O(n log n) 的由来
分治是全课程第一个真正的算法设计范式，也是后面动态规划、贪心、优化的对照基准。它听起来只有"分—解—合"三个字，但真正的难点在于：怎么分才能让子问题规模均衡、合并代价足够低。分得不均衡，复杂度立刻从 O(n log n) 掉到 O(n²)；合并写不出线性代价，整个算法就白分。这一章学完，应当能对一个新的分治算法写出递归式并解出量级。
一、递归：两个要素与调用栈
递归是函数直接或间接调用自身。它只有两个要素：
- 基例（边界条件）：规模小到可以直接求解，必须存在且能被到达。
- 递归步：把原问题化为规模更小的同类子问题，并保证每次规模严格减小。
缺基例会栈溢出，规模不减小会死循环，这两条是递归题最常见的错误来源。
运行时每次调用在调用栈上压入一个栈帧（参数、局部变量、返回地址）。递归深度 d 对应 O(d) 的辅助空间，这正是归并排序空间为 O(n) 而快排为 O(log n) 的原因。递归与栈是等价的：任何递归都能手写成显式栈的迭代版本，反之亦然。
三个经典实例：
- 阶乘：f(n) = n·f(n−1)，f(0) = 1，时间 O(n)，空间 O(n)。
- 汉诺塔：先把 n−1 个盘移到辅助柱，移最大的盘，再把 n−1 个盘移回目标柱，T(n) = 2T(n−1) + 1 = 2ⁿ − 1。
- 整数划分：把 n 拆成不超过 m 的整数之和，记 q(n, m)。递推为 q(n, m) = q(n, m−1) + q(n−m, m)，前者表示不用 m、后者表示至少用一个 m；基例 q(n, 1) = 1、q(1, m) = 1。朴素递归会重复计算大量子问题，加一张记忆表就是第 3 章的备忘录方法。
估算递归代价的通用工具是递归树：每个结点代表一次调用的非递归开销，把所有结点开销求和。汉诺塔的树是满二叉树，结点数 2ⁿ − 1；归并排序的树每层总开销都是 O(n)，共 log n 层，所以是 O(n log n)。画得出树，就估得出阶，这比背公式可靠。
二、分治法的三个步骤
分解（divide）：把规模 n 的问题划成 k 个规模 n/k 左右的子问题。 求解（conquer）：递归求解各子问题，规模足够小时直接算。 合并（combine）：把子问题的解拼成原问题的解。
一般的递归式为 T(n) = kT(n/m) + f(n)，f(n) 是分解加合并的代价。用主定理判断：
| 递归式形态 | 结果 | 典型算法 |
|---|---|---|
| T(n) = 2T(n/2) + O(n) | O(n log n) | 归并排序、最接近点对 |
| T(n) = 2T(n/2) + O(1) | O(n) | 二分搜索的递归形式 |
| T(n) = T(n/2) + O(1) | O(log n) | 二分搜索、快速幂 |
| T(n) = 2T(n/2) + O(n²) | O(n²) | 合并代价过高的反例 |
| T(n) = T(n−1) + O(n) | O(n²) | 快排最坏情况 |
判断要点：合并代价 f(n) 与子问题个数 k 的相对大小决定量级。f(n) 是多项式且"叶子贡献占优"时，总代价由叶子层决定；每一层代价相同（如归并的每层合并都是 O(n)）时，得到 log n 层 × O(n)。
三、二分搜索与大整数乘法
二分搜索：在有序数组 a[1..n] 中查找 x。取中点 mid，比较后把区间折半。递归式 T(n) = T(n/2) + O(1)，解得 O(log n)。前提是随机访问，链表上定位中点要 O(n)，总代价退化为 O(n)。这是 ADT 选择影响复杂度的最直接例子。
大整数乘法（Karatsuba）：两个 n 位二进制数相乘，朴素竖式要 O(n²) 次一位乘法。把每个数拆成高低两半 X = A·2^(n/2) + B，Y = C·2^(n/2) + D，则
XY = AC·2ⁿ + (AD + BC)·2^(n/2) + BD
直接算需要 4 次 n/2 位乘法，T(n) = 4T(n/2) + O(n) = O(n²)，没有改进。关键一步是用
AD + BC = (A + B)(C + D) − AC − BD
把 4 次乘法压到 3 次，得 T(n) = 3T(n/2) + O(n)。由主定理（3 > 2¹），T(n) = O(n^log₂3) ≈ O(n^1.585)。这是"减少子问题个数比减少合并代价更值钱"的最好例证。
四、排序中的分治
归并排序：从中间切开，两侧递归排好，再一次线性归并。T(n) = 2T(n/2) + O(n)，最好、平均、最坏都是 O(n log n)，空间 O(n)，稳定。归并的每层合并总代价恰好是 O(n)，共 log n 层，这是 O(n log n) 最干净的推导。
快速排序：以基准划分，左小右大，再递归两侧。划分代价 O(n)，但两侧规模取决于基准：
- 均衡划分（每层 1:1）：T(n) = 2T(n/2) + O(n) = O(n log n)
- 极端划分（1:n−1）：T(n) = T(n−1) + O(n) = O(n²)
平均 O(n log n)，最坏 O(n²)，空间 O(log n)（最坏 O(n)）。划分不均衡是唯一的性能杀手，所以优化都围绕基准选择：随机基准、三数取中。
线性时间选择：求第 k 小元素。快排的划分本身能定位基准的最终名次，只递归一侧即期望 O(n)；但要最坏 O(n)，需要"五分化中"：把 n 个数每 5 个一组，取每组中位数，再递归求这些中位数的中位数 M 作基准。此时至少有 3n/10 个元素小于 M、3n/10 个大于 M，递归式为
T(n) ≤ T(n/5) + T(7n/10) + O(n)
因 1/5 + 7/10 = 9/10 < 1，解得 T(n) = O(n)。这个结论反直觉的地方在于：找中位数本身要递归两次，却仍是线性的，因为子问题规模按几何级数衰减。
五、二维最接近点对
一维情形：排序后只比较相邻点，O(n log n)。二维不能照搬，需要分治 + 分带：
- 按 x 坐标中位数把点集分成左右两半，各自递归求最小距离 d₁、d₂，取 d = min(d₁, d₂)。
- 合并时只需考察中位线两侧宽 d 的竖直带。带内按 y 排序，每个点只需与其后至多 7 个点比较——因为带内任意 d×2d 的矩形最多容纳 8 个两两距离不小于 d 的点。
- 合并代价 O(n)，总递归式 T(n) = 2T(n/2) + O(n) = O(n log n)。
若合并时对带内点重新排序，代价变 O(n log n)，总体退化为 O(n log²n)。正确做法是在递归返回时顺带按 y 归并，把排序代价摊到合并里。
六、分治的适用判据
能用分治的问题通常满足三条：问题可分成规模更小的同类子问题；子问题的解可合并；子问题相互独立（不重叠）。第三条是分治与动态规划的分水岭——一旦子问题大量重叠，分治会指数级重复计算，此时应改用第 3 章的动态规划。
易错点
- 二分搜索写成
mid = (low + high) / 2在大数下溢出，应写low + (high − low) / 2。 - 归并排序的合并忘记处理某一侧剩余元素。
- 快排对已排序数组取首元素为基准，稳定退化到 O(n²)。
- 线性时间选择漏掉"每组 5 个"这个常数，分组数取错会导致递归式不收敛。
- 最接近点对合并时对带内点重新全排序，复杂度多一个 log。
这一章在整门课里的位置
本章建立在第 1 章的渐进记号与递归描述之上，是后续所有章节的方法论底座：第 3 章的动态规划就是把"重叠子问题"从分治里救出来，第 5、6 章的回溯与分支限界本质是"带剪枝的穷举分治"，第 10 章的分治优化与决策单调性更是直接复用本章的递归式分析。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲