algorithm - "closest pair of points"有哪些示例？

Question

我正在寻找“最近点对问题”的激励示例

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

这本身就是一个非常不言自明的问题，但我找不到一个合理的案例，在 o (n^{2 ).}

有什么建议吗？

Answer 1

在 O(n^2) 上使用 O(nlogn) 算法的合理情况是处理如此大量的元素以至于 O(n^2) 比 O(nlogn) 花费更多时间执行的每种情况。例如，100万个元素的蛮力O(n^2)可能需要半小时左右才能解决，而占卜O(nlogn)算法只需要几秒钟。一种快速查看差异的方法 (100 万 ^2) 和 (100 万 * log2(100 万))，您可以看到那里的巨大差异。