1.何为分治？何为减治？
分治法就是把一个大问题拆成很多小问题，然后分别解决，最后归并。
分治法一般有三个步骤：划分-求解-合并。
减治就是把问题划归为一个小问题，得到原问题解。
2.二分查找最值
输入：数组$A$
输出：数组中的最大值$Max$、最小值$Min$
划分：把$A$对半拆分，使拆分得到的每个小数组长度不超过2。
求解：对于每个数组都找出最大最小值。不断比较。
合并：无需合并，最后输出的数就是最终结果。
最终比较的次数为$\frac{3n}{2}-2$：
根据下面的图示：
列出比较次数的递推方程：
$$
T(n)=2T(\frac{n}{2})+2
$$
加2是因为两半数组比较之后，还要比较输出的最大最小值，由迭代法求得：
$$
T(n)=\frac{3n}{2}-2
$$
3.二进制大整数乘法
输入：n位二进制整数$X,Y$
输出：$X,Y$的乘积
通常分治复杂性为$O(n^2)$，改进分治法可以把复杂度改为$O(n^{1.59})$。
通常分治法
划分：将$X,Y$各自对半分，产生$A,B,C,D$。
求解&合并：计算$AC,AD,BC,BD$，再计算$AD+BC$，将$AC$左移n位，$AD+BC$左移$\frac{n}{2}$位，从而计算。
时间复杂性为：
$$
T(n)=4T(\frac{n}{2})+O(n)\to T(n)=O(n^2)
$$
改进分治法
这样分割完后，只需要计算$AC,BD,(A+B)(C+D)$即可。
根据$Master$定理，时间复杂性为：
$$
T(n)=3T(\frac{n}{2})+O(n)\to T(n)=O(n^{1.59})
$$
4.快速排序
输入：数组$A$
输出：排好序的数组$B$
划分：将数组依照一个参考点$A[i]$分割为两个部分，将比$A[i]$小的元素放在其左，比它大的放在其右。
求解：递归划分。
合并：无需合并，直接输出即可。
最好情况：每次分割，都将数组分割为两个相等的子集合：
$$
T(n)=2T(\frac{n}{2})+\theta (n)\to T(n)=\theta(nlogn)
$$
$\theta(n)$是因为每次分割都要把数组中的元素同分割点作比较，时间复杂度为$\theta(n)$。
最坏情况：每次分割，所有元素都落在一边：
$$
T(n)=T(n-1)+\theta(n)\to \theta(n^2)
$$
平均复杂性为$O(nlogn)$。
5.中位数和顺序统计量
输入：由$n$个数构成的多重集合$S$和数$k$
输出：$S$中第$k$小的元素$x$
划分：分组，每组5个数，最后一组可能小于5个数，用$+\infty$补足。$O(n)$，一次循环即可解决。
求解：每组数分别插入排序选出中位数($O(n)$)，递归地排序所有中位数($T(\frac{n}{5})$)，并得出所有中位数的中位数$p$。
这样，根据上图我们把$S$划分为三个集合$S_1,S_2,S_3$，它们中的元素分别小于、等于、大于$p$。$O(n)$
合并：如果$|S_1|\geq k$，递归地在$S_1$中搜索$x$；否则，如果$|S_1|+|S_2|\geq k$，$x=p$；否则，$k’=k-|S_1|-|S_2|$，递归地在$S_3$中搜索第$k’$小元素。这一步花费是$T(\frac{3n}{4})$，看上面那张图，合并这一步至少删除了$\frac{n}{4}$个元素，只需要在$\frac{3n}{4}$个元素中进行操作。
时间复杂性：
$$
T(n)=T(\frac{3n}{4})+T(\frac{n}{5})+O(n)\to T(n)=O(n)
$$
6.最邻近点对
输入：欧氏空间上$n$个点的集合$Q$
输出：$Q$中欧氏距离最近的两个点$A,B$
划分：按照横/纵坐标对各个点进行排序，求解出中位数$m$。依据之将$Q$分割成两个集合$Q_1,Q_2$，两个集合内的坐标点的横/纵坐标分别小于、大于$m$。
求解：如果最后划分的集合中只有两个点，就返回这两个点，否则，递归划分。
合并：在选择最邻近点的时候，不仅要考虑分割得到的集合，也要考虑分割点和其他点形成的点对。具体怎么实现？首先得到$Q_1,Q_2$中的最短距离$d$，然后在$m\pm d$的范围内寻找是否存在$d’<d$。最多有六个这样的点，证明如下：
时间复杂性：
$$
T(n)=2T(\frac{n}{2})+O(n)\to T(n)=O(nlogn)
$$