c# - 一系列 xy 坐标中的最短距离

Question

我有一个任务，它比较了一个问题的 2 种不同算法。这是问题所在：

假设我有一系列这样的 xy 坐标：

A(2,3)、B(5,6)、C(7,8)、D(6,2)、E(5,5)等。

我想找到它们之间距离最短的2个坐标。一种解决方案是使用蛮力（一一匹配），但还有另一种使用“分而治之”方法的解决方案。

你能帮我用“分而治之”的方法吗？

Answer 1

递归分治法的工作原理如下：

1) 根据 x 坐标对点进行排序。
2) 通过垂直线 x=xmid 将点集分成两个大小相等的子集。

3) 在左右子集中递归求解问题。这
分别产生左侧和右侧最小距离 dLmin 和 dRmin。

4) 求一对点之间的最小距离dLRmin，其中一个点位于分界线的左侧，第二个点位于右侧。

5) 最终答案是 dLmin、dRmin 和 dLRmin 中的最小值。（来源）

它的复杂度为O(n log n). 这里还有一个伪代码实现和这里方法的可视化描述。

Answer 2

想想“划分”和“合并”部分的含义。显然，“划分”意味着将问题分成两个较小的独立问题。如何？然后，鉴于您解决了两个较小的问题，您如何将它们合并在一起？这两种方法的时间复杂度是多少？如果您需要更多说明，请发表评论。