C++实现利用分治算法编程实现最近点对问题，并进行时间复杂性分析

最近点对问题是指在一个平面上给定n个点，找出其中距离最近的两个点。下面是C语言实现分治算法解决最近点对问题的代码，同时也进行了时间复杂性分析。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 定义点结构体
typedef struct point {
    double x;
    double y;
} point;

// 计算两个点之间的距离
double distance(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    point *p1 = (point *)a;
    point *p2 = (point *)b;
    return (p1->x > p2->x);
}

// 分治算法实现
double closest_pair(point *points, int n) {
    // 如果点数小于等于3，直接计算并返回最小距离
    if (n <= 3) {
        double min_distance = INFINITY;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double d = distance(points[i], points[j]);
                if (d < min_distance) {
                    min_distance = d;
                }
            }
        }
        return min_distance;
    }

    // 分别对左右两部分进行递归
    int mid = n / 2;
    double d1 = closest_pair(points, mid);
    double d2 = closest_pair(points + mid, n - mid);
    double d = fmin(d1, d2);

    // 取中间线左右d范围内的点进行判断
    point *strip = (point *)malloc(sizeof(point) * n);
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (fabs(points[i].x - points[mid].x) < d) {
            strip[j++] = points[i];
        }
    }

    // 在strip中找出距离最小的点对
    for (int i = 0; i < j; i++) {
        for (int k = i + 1; k < j && strip[k].y - strip[i].y < d; k++) {
            double d3 = distance(strip[i], strip[k]);
            if (d3 < d) {
                d = d3;
            }
        }
    }
    free(strip);
    return d;
}

int main() {
    int n;
    printf("请输入点的数量：");
    scanf("%d", &n);
    point *points = (point *)malloc(sizeof(point) * n);
    for (int i = 0; i < n; i++) {
        printf("请输入第%d个点的x坐标和y坐标：", i + 1);
        scanf("%lf%lf", &points[i].x, &points[i].y);
    }
    qsort(points, n, sizeof(point), cmp);
    double min_distance = closest_pair(points, n);
    printf("最近点对的距离为：%.2lf\n", min_distance);
    free(points);
    return 0;
}

时间复杂性分析：

对于n个点的情况，分治算法的时间复杂度为O(nlogn)。具体来说：

- 排序的时间复杂度为O(nlogn)；
- 分别递归处理左右两部分的时间复杂度为2T(n/2)；
- 合并左右两部分的时间复杂度为O(n)；
- 在中间区域中查找最近点对的时间复杂度为O(nlogn)。

因此，总的时间复杂度为T(n) = 2T(n/2) + O(nlogn)，根据主定理，可以得到T(n) = O(nlogn)。