找出平面上最近的点对：蛮力法与分治法实现及性能比较

问题描述：

设p1=(x1, y1), p2=(x2, y2), ..., pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

要求：

分别用蛮力法和分治法求解最近对问题
输入是平面上的N个点，输出是最近点对距离。
要求随机生成N个点的平面坐标。
分别对N=100，1000，3000，给出相应的C语言代码, 统计算法运行时间(微秒)，分析算法的时间性能。

一、蛮力法实现代码：

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

#define MAX_X 1000
#define MAX_Y 1000

typedef struct Point {
    int x;
    int y;
} Point;

double distance(Point p1, Point p2) {
    return sqrt(pow((p1.x - p2.x), 2) + pow((p1.y - p2.y), 2));
}

double bruteForce(Point points[], int n) {
    double minDistance = INFINITY;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double dist = distance(points[i], points[j]);
            if (dist < minDistance) {
                minDistance = dist;
            }
        }
    }
    return minDistance;
}

int main() {
    srand(time(NULL));
    int n = 100; // 设置点的个数
    Point points[n];
    for (int i = 0; i < n; ++i) {
        points[i].x = rand() % MAX_X;
        points[i].y = rand() % MAX_Y;
    }
    
    clock_t start = clock();
    double minDistance = bruteForce(points, n);
    clock_t end = clock();
    
    double timeUsed = ((double) (end - start) / CLOCKS_PER_SEC) * 1000000;
    
    printf("最近点对距离：%.2f\n", minDistance);
    printf("算法运行时间：%f微秒\n", timeUsed);
    
    return 0;
}

二、分治法实现代码：

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

#define MAX_X 1000
#define MAX_Y 1000

typedef struct Point {
    int x;
    int y;
} Point;

double distance(Point p1, Point p2) {
    return sqrt(pow((p1.x - p2.x), 2) + pow((p1.y - p2.y), 2));
}

double min(double x, double y) {
    return (x < y) ? x : y;
}

double stripClosest(Point strip[], int size, double d) {
    double minDistance = d;
    
    for (int i = 0; i < size; ++i) {
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDistance; ++j) {
            double dist = distance(strip[i], strip[j]);
            if (dist < minDistance) {
                minDistance = dist;
            }
        }
    }
    
    return minDistance;
}

double closestUtil(Point points[], int n) {
    if (n <= 3) {
        return bruteForce(points, n);
    }
    
    int mid = n / 2;
    Point midPoint = points[mid];
    
    double dl = closestUtil(points, mid);
    double dr = closestUtil(points + mid, n - mid);
    
    double d = min(dl, dr);
    
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip[j] = points[i];
            j++;
        }
    }
    
    return min(d, stripClosest(strip, j, d));
}

double closest(Point points[], int n) {
    qsort(points, n, sizeof(Point), compareX);
    
    return closestUtil(points, n);
}

int main() {
    srand(time(NULL));
    int n = 100; // 设置点的个数
    Point points[n];
    for (int i = 0; i < n; ++i) {
        points[i].x = rand() % MAX_X;
        points[i].y = rand() % MAX_Y;
    }
    
    clock_t start = clock();
    double minDistance = closest(points, n);
    clock_t end = clock();
    
    double timeUsed = ((double) (end - start) / CLOCKS_PER_SEC) * 1000000;
    
    printf("最近点对距离：%.2f\n", minDistance);
    printf("算法运行时间：%f微秒\n", timeUsed);
    
    return 0;
}

三、时间性能分析：

蛮力法的时间复杂度为O(n^2)，分治法的时间复杂度为O(nlogn)。从时间复杂度上来看，分治法的效率更高。

对于N=100，蛮力法和分治法的运行时间差异不大；对于N=1000，蛮力法的运行时间较长，分治法的运行时间明显缩短；对于N=3000，蛮力法的运行时间进一步增加，而分治法的运行时间仍然保持较短。

因此，随着点的个数增加，分治法的优势更为明显。分治法通过将问题划分为子问题进行求解，减少了不必要的计算量，提高了算法的效率。