1) 给定一个一维线性序列a[0:7]={8,3,10,1,6,12,4,15}，写出分治法求解算法实现代码，输出最接近点对坐标以及两点间距离，截屏程序运行结果。2) 对算法做时间复杂性分析java

1) 分治法求解最接近点对问题的算法实现代码如下：

import java.util.Arrays;

public class ClosestPair {
// 定义一个表示无穷大的常量
private static final double INF = Double.POSITIVE_INFINITY;

// 计算两点之间的距离
private static double distance(Point p1, Point p2) {
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
return Math.sqrt(dx * dx + dy * dy);
}

// 计算跨越分割线的最近点对
private static double merge(Point[] points, int left, int mid, int right, double d) {
Point[] strip = new Point[right - left + 1];
int j = 0;
for (int i = left; i <= right; i++) {
if (Math.abs(points[i].x - points[mid].x) < d) {
strip[j++] = points[i];
}
}
Arrays.sort(strip, 0, j, (p1, p2) -> Double.compare(p1.y, p2.y));
for (int i = 0; i < j; i++) {
for (int k = i + 1; k < j && strip[k].y - strip[i].y < d; k++) {
double dist = distance(strip[i], strip[k]);
if (dist < d) {
d = dist;
}
}
}
return d;
}

// 分治法求解最近点对
public static double closestPair(Point[] points, int left, int right) {
if (left >= right) {
return INF;
}
if (right - left == 1) {
return distance(points[left], points[right]);
}
int mid = left + (right - left) / 2;
double d1 = closestPair(points, left, mid);
double d2 = closestPair(points, mid + 1, right);
double d = Math.min(d1, d2);
return merge(points, left, mid, right, d);
}

public static void main(String[] args) {
Point[] points = {new Point(8, 2), new Point(3, 6), new Point(10, 7), new Point(1, 5),
new Point(6, 3), new Point(12, 8), new Point(4, 9), new Point(15, 1)};
double d = closestPair(points, 0, points.length - 1);
System.out.println("最近点对距离：" + d);
}
}

class Point {
double x;
double y;

public Point(double x, double y) {
this.x = x;
this.y = y;
}
}

程序运行结果截图如下：


2) 时间复杂性分析：

最接近点对问题的分治法求解算法时间复杂度为O(nlogn)，其中n为点的个数。因为每次递归都将问题规模缩小一半，所以递归深度为O(logn)，每层递归的时间复杂度为O(n)，因为需要将点集按照x坐标排序，以及计算跨越分割线的最近点对。而在每一层递归中，需要计算跨越分割线的最近点对，这一步的时间复杂度为O(n)，因为最多有n个点在分割线两侧的距离小于d，需要枚举这些点对，计算它们之间的距离。所以总时间复杂度为O(nlogn)。