1

我在雅虎被问到机器学习简介这个问题。给定一组点 (x,y) 坐标，我被要求在 O(n) 或 O(log n ) 时间内找到距离最短的点。显然，我能够想出 O(n^2) 时间，但离获得更好的算法还差得很远。尽管问题陈述是分而治之，但我还是想不出合并步骤的理由。我还在互联网上搜索了这个问题，发现它实际上很受欢迎，但我仍然无法掌握合并步骤的推理。

谁能帮我解决这个问题？

输入：(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)

4

1 回答 1

5

可以使用递归分治法在 O(n log n) 时间内解决该问题，例如，如下所示：

1.根据x坐标对点进行排序。

2. 用一条垂直线 x=xmid 将一组点分成两个大小相等的子集。

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

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

5.最终答案是dLmin、dRmin和dLRmin中的最小值。

http://en.wikipedia.org/wiki/Closest_pair_of_points

于 2012-09-05T15:02:27.630 回答