Dud*_*ude 1 algorithm performance time-complexity data-structures
我在雅虎被问到机器学习档案这个问题.给定一组点(x,y)坐标,我被要求找到O(n)或O(log n)时间内距离最小的点.显然我能够拿出O(n ^ 2)时间但是没有办法接近获得更好的算法.即使问题陈述是为分裂和征服而尖叫,我也无法想出合并步骤的原因.我也在互联网上搜索这个问题并发现它实际上非常受欢迎,但我仍然无法掌握合并步骤的推理.
任何人都可以帮我解决这个问题吗？
输入:(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)
使用递归分而治之的方法可以在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