3.8给定n个点，其坐标为(x,y)(0≤i≤n-1),要求使用分治策略求解设计算法，找出其中距 离最近的两个点。两点间的距离公式为:√(x-x,)2+(y,-y,)2 特点以 (1)写出算法的伪代码; (2)编写js程序实现这一算法; 而这些于 (3)分析算法的时间复杂度。

为了使用分治策略解决这个问题，我们可以采用二分查找法的思想，将整个数据集不断分成两半，并递归地在每个子集中找到最接近的两个点。以下是算法的基本步骤：

1. 算法的伪代码:

function findNearestPoints(points, low, high):
   if low == high:
       return [points[low], points[low]]  // 如果只有一个点，直接返回
   mid = (low + high) / 2
   leftResult = findNearestPoints(points, low, mid)
   rightResult = findNearestPoints(points, mid+1, high)

   # 检查左半部分和右半部分的最小距离
   nearestLeft = leftResult[0]
   nearestRight = rightResult[0]
   if dist(leftResult[1], points[mid]) < dist(nearestLeft, nearestRight):
      nearestRight = points[mid]

   # 返回合并后的结果
   return [nearestLeft, nearestRight]

function main(points):
   n = len(points)
   return findNearestPoints(points, 0, n - 1)

2. JavaScript 实现:

function findNearestPoints(points, low, high) {
    if (low === high) return [points[low], points[low]];
    const mid = Math.floor((low + high) / 2);
    const leftResult = findNearestPoints(points, low, mid);
    const rightResult = findNearestPoints(points, mid + 1, high);

    let nearestLeft = leftResult[0];
    let nearestRight = rightResult[0];

    if (distance(leftResult[1], points[mid]) < distance(nearestLeft, nearestRight)) {
        nearestRight = points[mid];
    }

    return [nearestLeft, nearestRight];
}

function distance(pointA, pointB) {
    return Math.sqrt(Math.pow(pointA[0] - pointB[0], 2) + Math.pow(pointA[1] - pointB[1], 2));
}

function main(points) {
    const n = points.length;
    return findNearestPoints(points, 0, n - 1);
}

3. 时间复杂度分析:
- 对于每次划分，我们处理了数组的一半。因此，总的操作次数是 O(log n)，因为我们需要对每个元素进行log(n)次比较。
- 而对于每一步的查找操作，我们都是线性的，即O(n)。但由于我们在递归过程中同时进行左右子集的搜索，总时间复杂度仍然是 O(n log n)，因为最坏情况下每个节点都要被访问一次。