分治策略适用性分析

先给出一个结论： 分治算法的本质，是以增加 $O(logn)$ 的对数级复杂度因子为代价，换取在合并阶段利用子问题性质进行降维优化的空间。

接下来我们以一些经典的问题来解释这个结论。

平面最近点对

为了将二维几何问题转化为一维序列问题，我们首先对所有的点按照横坐标（X轴）升序排序，在此有序序列的基础上再来设计分治策略。

对于区间 $[l,r]$ , 其中点为 $mid=(l+r)/2$ 。令 $g(l,r)$ 表示序列中区间 $[l,r]$ 内两点之间的最近距离。与最大子段和的分治策略类似，该区间内的最近点对仅可能出现在以下三种情况中：

两个点均位于左半区间 $[l,mid]$ 。
两个点均位于右半区间 $[mid+1,r]$ 。
跨越边界：一个点位于左半区间，另一个点位于右半区间。

在合并时如果我们采用最直观的想法：处理第三种情况时，暴力枚举左区间和右区间的所有点对进行计算，那么合并步骤的时间代价为: $(n/2)^2$ ，总时间复杂度的递推式为： $T(n)=2*T(n/2)+(n/2)^2$ ，可推出总时间复杂度为： $O(n^2)$ 。这与全局暴力枚举的复杂度完全一致，甚至由于递归调用的开销，常数反而更大。显然，这种无效分治并不优秀。

正如我们在本小节所抛出的结论，必须利用“子问题性质”来优化合并过程。我们已经递归求出了左、右半区间的最近距离，令其最小值为 $d=min(g(l,mid),g(mid+1,r))$ 。这个 $d$ 就是优化合并过程的宝贵条件：假定 $mid$ 点的横坐标为 $X_{mid}$ ，在寻找跨越中线的点对时，只有那些距离严格小于 $d$ 的点对才有意义。基于此，我们可以进行两次强力剪枝：

$X$ 轴剪枝(确定带状区域)：

我们只需保留横坐标落在 $[X_{mid}-d,X_{mid}+d]$ 范围内的点。横坐标距离中线大于 $d$ 的点不可能与另一侧的点组合出小于 $d$ 的距离。
$Y$ 轴剪枝：

将上述带状区域内保留下来的点，按照 $Y$ 轴升序排序。对于该区域任意一点 $P$ ，可以严格证明在 Y 轴上与 $P$ 点距离在 $d$ 范围内的点，最多只有7个。

对于第2个剪枝，我们使用鸽巢原理给出严格证明：

假定我们现在拿到了 $X$ 轴剪枝以后的带状区域(宽度为 $2*d$ ，即 $X_{mid}-d$ 到 $X_{mid}+d$ )内的一个点 $P(x,y)$ ，我们只需要寻找排在它后面的点(因为已经按照 $Y$ 轴排序，且 $P$ 点前面的点已经在向后枚举的过程中考虑过了 $P$ 点)。我们要找的点与 $P$ 的距离必须 $<d$ ，所以候选点 $Q$ 的 $Y$ 轴坐标 $Y_{Q} \le Y_{P}+d$ ，因此可以得出结论：对于点 $P$ ，真正需要检查的候选点，全部落在一个宽为 $2*d$ 、高为 $d$ 的矩形内。

以 $X_{mid}$ 为中线，将这个 $2d \times d$ 的大矩形从中间切开，变成左右两个 $d \times d$ 的正方形，问题转化成了左、右侧的 $d \times d$ 的矩形中最多可以放进多少个点，保证任意两个点之间的距离 $\ge d$ (在分治的过程我们已经保证了位于同一侧的节点之间的距离 $\ge d$ )。由鸽巢原理可知，最多容纳 $4$ 个点，分别为正方形的四个顶点。左侧正方形4个点，右侧同样有4个点，去掉 $P$ 点本身，剩余7个点，证毕。

这里画个图：

依据上述思路，我们给出该问题的实现代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
const double INF=2e20;
int n, tmp[N];
struct node{
    double x, y;
    friend bool operator<(node a,node b){ //按x排序
        return a.x<b.x;
    }
}tnode[N];

bool cmp(int i, int j){//按y排序
    return tnode[i].y<tnode[j].y;
}

double dist(int i, int j){//计算距离函数
    return sqrt((tnode[i].x-tnode[j].x)*(tnode[i].x - tnode[j].x)
                +(tnode[i].y-tnode[j].y)*(tnode[i].y-tnode[j].y));
}
double merge(int l, int r){
    if(l==r) return INF;
    if(l+1==r) return dist(l, r); //区间中只剩两个点直接返回距离
    int mid=(l+r)/2;
    double d=min(merge(l,mid), merge(mid+1,r));
    int cnt=0;
    //X轴剪枝，确定带状区域
    for(int i=l; i <= r; i++)
        if(fabs(tnode[mid].x-tnode[i].x)<d)
            tmp[++cnt]=i;
    sort(tmp+1,tmp+1+cnt,cmp);//对筛选出来的X轴合法点按照Y轴排序
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt && tnode[tmp[j]].y-tnode[tmp[i]].y<d;j++) //Y轴剪枝
            d=min(d,dist(tmp[i],tmp[j]));
    return d;
}
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%lf%lf", &tnode[i].x, &tnode[i].y);
    sort(tnode, tnode+1+n);
    printf("%.4lf\n", merge(1,n));
    return 0;
}

时间复杂度分析：

在合并阶段，我们首先筛选出横坐标落在 $[X_{mid}-d, X_{mid}+d]$ 带状区域内的点（耗时 $O(n)$ ），随后对这些候选点按 $Y$ 轴坐标进行排序（最坏情况下带状区域包含所有点，耗时 $O(n \log n)$ ）。排序完成后，得益于鸽巢原理，每个点最多只需向下检查 7 个相邻点（耗时 $O(n)$ ）。

因此，单次合并阶段的总时间开销被排序操作所主导，即为 $O(n \log n)$ 。由于分治过程每次将原问题一分为二，整个算法的时间复杂度递推关系式可表示为：$$T(n) = 2T(n/2) + O(n \log n)$$，通过递归树法或主定理展开化简，可得最终的时间复杂度为： $T(n) = O(n \log^2 n)$ 。

极致优化：

事实上，该问题还存在进一步优化的空间。如果在合并过程中，我们不依赖代价较高的快速排序，而是采用类似归并排序的思想——在递归返回局部最短距离的同时，利用双指针将左右两个已按 $Y$ 轴有序的子点集进行 $O(n)$ 线性合并，那么单次合并的时间开销将降至 $O(n)$ 。此时递推式优化为 $T(n) = 2T(n/2) + O(n)$ ，整个算法的总时间复杂度将达到理论最优的 $O(n \log n)$ 。具体的归并细节实现，留给读者作为进阶挑战自行思考与补全。