概念

分治算法由两部分组成：
分（divide）：递归解决较小的问题。
治（conquer）：然后从子问题的解构建原问题的解。

一般坚持子问题是不相交的，即基本上不重叠。

分治算法的运行时间

所有有效的分治算法都是把问题分成一些子问题，每个子问题都是原问题的一部分，然后进行某些附加的工作以算出最后的答案。

比如归并排序通过将原问题分解为两个子问题，每个子问题均为原问题大小的一半，然后用到O(N)的附加工作。由此得到递归运行时间方程： $T(N)=2T(N/2)+O(N)$ 该方程的解为 $O(NlogN)$ 。

更加一般的分治算法的运行时间满足如下定理：

最近点问题

对于平面上的点列P，我们需要找到一对最近的点。如果存在N个点，那么就存在N(N-1)/2对点间的距离。我们可以检查所有这些距离，不过这是一个花费 $O(N^2)$ 的算法。

分治的做法：假设这些点已经按照x坐标排序，那么就可以画一条想象的垂线，把点集分成两半： $P_{L}$ 和 $P_{R}$ 。最近的一对点要么在 $P_{L}$ 中，要么在 $P_{R}$ 中，或者一个点在 $P_{L}$ 中一个点在 $P_{R}$ 中。可以将这三个距离分别叫做 $d_{L}$ 、 $d_{R}$ 、 $d_{C}$ 。由上面的定理可知，如果一个过程由两个一半大小的递归调用和附加的O(N)工作组成，那么总的时间将是 $O(NlogN)$ 。

令 $\delta =min(d_{L},d_{R})$ ，所以我们只需计算 $min(\delta,d_{C} )$ ，并且需要在O(N)的时间复杂度内完成。

1）如果 $d_{C}$ 小于 $\delta$ ，那么决定 $d_{C}$ 的两个点必然在分割线的 $\delta$ 距离内。

2）决定 $d_{C}$ 的两个点的y坐标相差最多是 $\delta$ 。

于是给出计算 $min(\delta,d_{C} )$ 的伪代码，假设带中的点按照它们的y坐标排序：

对于任意的点 $p_{i}$ ，在最坏的情形下最多有7个点 $p_{j}$ 被考虑。所以尽管上述的代码有两重for循环，但实际的复杂度只有O(N)。为了解决上面假设y坐标排序已经是现成的问题，我们将保留两个表。一个是按照x坐标排序的点的表P，而另一个是按照y坐标排序的点的表Q。这两个表可以通过一个预处理排序步骤完成。 $P_{L}$ 和 $Q_{L}$ 是传递给左半部分递归调用的参数表， $P_{R}$ 和 $Q_{R}$ 是传递给右半部分递归调用的参数表。当递归调用返回时，我们扫描Q表并删除其x坐标不在带内的所有点，此时Q只含有带中的点，并保证按照y坐标排序。