在一系列xy坐标的最短距离

Question

我有一个问题比较2种不同的算法的分配。这里的问题：

假设我有一个系列的XY COORDS这样的：

A（2,3），B（5,6），C（7,8），d（6,2），E（5,5）等。

我想找到2个COORDS具有它们之间的最短距离。一溶液的是使用蛮力（匹配逐一），但存在使用“分而治之”方法的另一溶液..

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

Answer 1

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

1）根据它们的x坐标排序点。 2）由垂直线X = xmid分割点的集合分成两个相等大小的子集。

3）在左边和右边的子集递归地解决这个问题。这个 产生了左侧和右侧的最小距离分别dLmin和dRmin。

4）求一对点，其中一个点位于垂直划分和第二点的左侧之间的最小距离dLRmin位于右侧。

5）最后的答案是dLmin，dRmin和dLRmin中最小的。 （source）

它有一个O(n log n)的复杂性。还有一个伪实施here和方法here的直观描述。

Answer 2

想想“分”和“合并”部分表示。显然，“分”是指划分问题分为2分较小单独的。怎么样？然后，给你解决了2个较小的问题，你如何合并在一起？什么是这两种方法的时间复杂度？如果你需要更多的澄清发表评论。