分治法可以将较大规模的问题分解成若干个与原问题相似的问题，求解后合并到原问题，从而优化复杂度。
- 确定问题模型
- 确定拆分（合并）性质
- 确定分治终点的解法
原理
| 步骤 | 作用 | 复杂度 |
|---|---|---|
| Divide | 整个问题划分为多个子问题 | $D(n)$ |
| Conquer | 求解各个子问题 | $\displaystyle a T \left( \frac{n}{b} \right)$ |
| Combine | 合并子问题的解，形成原问题的解 | $C(n)$ |
据此可建立递归方程：
$$T(n) = aT\left( \frac{n}{b} \right) + D(n) + C(n)$$二分法
二分法就是分治法的一种常见实现，核心是子问题的规模是原问题的 $\displaystyle \frac{1}{2}$
案例
归并排序
快速排序
折半查找
大整数乘法
$n$ 位二进制整数 $X$ 和 $Y$ 相乘
$$\begin{align*} XY &= (A \cdot 2^{\frac{n}{2}} + B) \cdot (C \cdot 2^{\frac{n}{2}} + D) \\ &= AC \cdot 2^n + (AD + BC) \cdot 2^{\frac{n}{2}} + BD \\ &= AC \cdot 2^{n} + ((A+B)(C+D)-AC-BD) \cdot 2^{\frac{n}{2}} + BD \end{align*}$$矩阵乘法
两个 $n \times n$ 的矩阵 $\bm{A}$ 和 $\bm{B}$ 相乘，普通计算方法的时间复杂度为 $\varTheta(n^3)$
将 $\bm{A}$ 和 $\bm{B}$ 分成 $4$ 个大小为 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵，则有
$$\left[ \begin{matrix} \bm{C}_{11} & \bm{C}_{12} \\ \bm{C}_{21} & \bm{C}_{22} \end{matrix} \right] = \left[ \begin{matrix} \bm{A}_{11} & \bm{A}_{12} \\ \bm{A}_{21} & \bm{A}_{22} \end{matrix} \right] \times \left[ \begin{matrix} \bm{B}_{11} & \bm{B}_{12} \\ \bm{B}_{21} & \bm{B}_{22} \end{matrix} \right] $$令
$$\left\{ \begin{array}{c} \begin{align*} \bm{M}_1 &= \bm{A}_{11} (\bm{B}_{12}-\bm{B}_{12}) \\ \bm{M}_2 &= (\bm{A}_{21} + \bm{A}_{12}) \bm{B}_{11} \\ \bm{M}_3 &= (\bm{A}_{21} + \bm{A}_{22}) \bm{B}_{11} \\ \bm{M}_4 &= \bm{A}_{22} (\bm{B}_{21} - \bm{B}_{11}) \\ \bm{M}_5 &= (\bm{A}_{11} + \bm{A}_{22}) (\bm{B}_{11} + \bm{B}_{22}) \\ \bm{M}_6 &= (\bm{A}_{12} - \bm{A}_{22}) (\bm{B}_{21} + \bm{B}_{22}) \\ \bm{M}_7 &= (\bm{A}_{11} - \bm{A}_{21}) (\bm{B}_{11} + \bm{B}_{12}) \end{align*} \end{array} \right.$$则有
$$\left\{ \begin{array}{c} \begin{align*} \bm{C}_{11} &= \bm{M}_5 + \bm{M}_4 - \bm{M}_2 + \bm{M}_6 \\ \bm{C}_{12} &= \bm{M}_1 + \bm{M}_2 \\ \bm{C}_{21} &= \bm{M}_3 + \bm{M}_4 \\ \bm{C}_{22} &= \bm{M}_5 + \bm{M}_1 - \bm{M}_3 - \bm{M}_7 \end{align*} \end{array} \right.$$第k小元素
若 $|S| \leqslant 50$，则采用堆排序
否则：
- 将 $n$ 个元素分为 $\lceil \frac{n}{5} \rceil$，每组5个元素，每组排序。
- 将每组第三个元素取出，得到大小为 $\lceil \frac{n}{5} \rceil$ 的数组 $M$。若最后一组中的元素可能不足5个，则1个取出、2个取较小、3个取中间、4个取第二小。
- $m = \text{select}(M, \lceil |M|/2 \rceil)$，时间复杂度 $T(\lceil n/5 \rceil)$，此时 $S$ 中至少有 $3\left( \lceil \frac{1}{2} \lceil \frac{n}{5} \rceil \rceil -2 \right) \geqslant \frac{3n}{10} - 6$ 个元素大于等于 $m$；至少有 $\frac{3n}{10}-6$ 个元素小于等于 $m$
- 依次扫描整个数组 $S$，当 $s_i < m$ 时放入 $S_1$，$s_i = m$ 时放入 $S_2$；$s_i > m$ 时放入 $S_3$。
- 当 $k \leqslant |S_1|$ 时，调用
select(S1, k)；当 $|S_1| < k \leqslant |S_1| + |S_2|$ 时，返回m；当 $k > |S_1| + |S_2|$ 时，调用select(S3, k-|S1|-|S_2|)
此时时间复杂度 $T(n) = T(\lceil \frac{n}{5} \rceil) + T(\frac{7n}{10} + 6) + O(n) \leqslant O(n)$
证明
最近点对
在二维平面上 $n$ 个点中找距离最近的两个点，
如果 $Q$ 中仅包含一个点，则算法结束；否则，把 $Q$ 中的点按 $x$ 和 $y$ 坐标值排序。
计算 $Q$ 中各点 $x$ 坐标的中位数 $m$，用垂线 $x=m$ 把 $P$ 划分为两个大小相等的子集和 $L$ 和 $R$。
递归地在 $L$，$R$ 中找出最近点对 $(p_1, p_2) \in L$，$(q_1, q_2) \in R$ 则 $d = \min \{\text{dis}(p_1, p_2), \text{Dis}(q_1, q_2)\}$
在临界区查找距离小于 $d$ 的点对 $(p_l, q_r)$，其中 $p_l \in L$，$q_r \in R$；如果找到，则 $(p_l, q_r)$ 是 $Q$ 中的最近点对，否则 $(p_1, p_2)$ 和 $(q_1, q_2)$ 中距离最小者为 $Q$ 中的最接近点对。
如何查找 $(p_l, q_r)$：
对于左临界区中任意一点 $P$，在右临界区中找一点 $Q$，若 $|PQ| < d$，则必有 $Q$ 位于右临界区。
极端情况下，若 $P$ 在中位线上，$Q$ 在绿色半圆中，不妨把 $D$ 扩大为 $d \cdot 2d$ 的矩形区域，这样区域内最多可能存在6个点，使得每两个点之间的距离大于 $d$，即对于任意一点 $P$，最多只需计算6次距离就可以了。
时间复杂度
$$T(n) = \left\{ \begin{matrix} \begin{align*} & O(1) \\ &2T\left(\frac{n}{2}\right) + O(n) \end{align*} \end{matrix} \right.$$则 $T(n) = O(n \log n)$
平衡
平衡与分治法密不可分，使用分治法和递归时要尽量把问题分成规模相等或至少是规模相近的子问题。