第 118B 章 分治的三步框架¶
本章配套 4 道例题，见 §例题。
状态：骨架。 本章目前只有分治的通用框架与主定理， 归并排序、最近点对、快速幂等具体算法尚未写入。
分治永远是同样的三步：划分、求解、合并。真正需要想的只有第三步—— 跨越中线的那部分答案，能不能在 \(O(n)\) 或 \(O(n\log n)\) 内算出来。 答得上来就能分治，答不上来就不能。
进阶形态（归并分治、整体二分、CDQ）建立在同一个框架上， 见 CDQ 分治 与 整体二分。
1 划分、求解、合并¶
分治（divide and conquer）永远是同样的三步：
| 步 | 名字 | 做什么 |
|---|---|---|
| 1 | 划分（divide） | 把规模 \(n\) 的问题分成若干个规模 \(n/b\) 的子问题 |
| 2 | 求解（conquer） | 递归解决子问题（规模足够小时直接算） |
| 3 | 合并（combine） | 把子问题的解拼成原问题的解 |
主定理给出复杂度：若 \(T(n) = a\,T(n/b) + f(n)\)，则
| 情形 | 结论 | 例子 |
|---|---|---|
| \(f(n) = O(n^{\log_b a - \epsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) | Karatsuba 乘法（\(a=3,b=2\)） |
| \(f(n) = \Theta(n^{\log_b a})\) | \(T(n) = \Theta(n^{\log_b a}\log n)\) | 归并排序（\(a=b=2, f=n\)）→ \(n\log n\) |
| \(f(n) = \Omega(n^{\log_b a + \epsilon})\) | \(T(n) = \Theta(f(n))\) | 合并代价占主导 |
分治题的全部工夫在第 3 步「合并」。 划分几乎总是「对半砍」，求解是递归调用，只有合并需要想。 判断一道题能不能分治，就是判断「跨越中线的那部分答案，能不能在 \(O(n)\) 或 \(O(n\log n)\) 内算出来」。
2 例题：四道题的「合并」长什么样¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BM5 | 合并k个已排序的链表 | 较难 | 题解 |
| BM12 | 单链表的排序 | 中等 | 题解 |
| BM20 | 数组中的逆序对 | 中等 | 题解 |
| BM47 | 寻找第K大 | 中等 | 题解 |
本章仍是骨架，归并排序、最近点对、快速幂的正文尚未写入。 但下面四道题可以先当作 §1 那句判据的检验场——每道题只问一件事：跨中线的贡献怎么算。
| 题 | 划分 | 跨中线要算的东西 | 合并代价 |
|---|---|---|---|
| BM20 数组中的逆序对 | 对半砍 | 左半的每个数与右半的每个数构成多少逆序对 | \(O(n)\)，随归并顺手数 |
| BM12 单链表的排序 | 快慢指针找中点断开 | 无（合并就是两条有序链表首尾接） | \(O(n)\) |
| BM5 合并k个已排序的链表 | 把 \(k\) 条链两两配对 | 无 | 每层 \(O(n)\)，共 \(\log k\) 层 |
| BM47 寻找第K大 | 按基准值把数组切成两段 | 无（第 \(k\) 大只落在其中一段） | \(O(n)\) 期望 |
前三道的合并步都是归并——其中单链表的排序划分时要用快慢指针找中点，与另两道按下标对半砍不同；第四道寻找第K大是只递归一侧的分治—— 它把 \(T(n)=2T(n/2)+O(n)\) 降成 \(T(n)=T(n/2)+O(n)\)， 按主定理的第三种情形直接得 \(\Theta(n)\) 期望，这就是快速选择比「排完再取第 \(k\) 个」更优的全部理由。
数组中的逆序对是归并分治这条支线的入门题：逆序对的定义天然按「左边一个、右边一个」拆开， 左半内部与右半内部的贡献由递归负责，剩下的跨中线部分在归并的同时就能数出来—— 右半弹出一个数时，左半剩下多少个未弹出的数，就贡献多少对。 同一套「在归并里顺手统计」的手法往上走就是 CDQ 分治。
合并k个已排序的链表值得单独说一句取舍：\(k\) 条链两两归并是 \(O(nk\log k)\) 里的 \(\log k\) 层， 而用堆维护 \(k\) 个表头是 \(O(n\log k)\)，两者同阶。 分治版不需要额外数据结构，堆版在 \(k\) 很小时常数更低。 堆的写法见 优先队列与堆。
3 本章速查¶
| 要点 | 结论 |
|---|---|
| 分治三步 | 划分 → 求解 → 合并 |
| 分治题的全部工夫 | 在「合并」这一步（划分几乎总是对半砍） |
| 判断能不能分治 | 「跨中线的贡献能不能在 \(O(n)\) / \(O(n\log n)\) 算出来」 |
| 主定理（\(a=b=2, f=n\)） | \(T(n)=\Theta(n\log n)\) |
| 递归深度 | 对半砍时只有 \(O(\log n)\approx17\)，Python 完全安全 |