algorithm - “最近的一对点”有哪些例子？

Question

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

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

就其本身而言，这是一个非常不言自明的问题，但我找不到一个合理的情况，即在 o (n ² ) 中的蛮力方法需要这种具有 o(n log n) 的算法。

有什么建议么？

Answer 1

在 O(n^2) 上使用 O(nlogn) 算法的合理情况是处理大量元素以致 O(n^2) 比 O(nlogn) 需要更多时间来执行的所有情况。例如，具有 100 万个元素的蛮力 O(n^2) 可能需要大约半小时才能解决，而神与征服 O(nlogn) 算法只需几秒钟。一种查看差异的非常快速的方法 (100 万 ^2) 和 (100 万 * log2(100 万))，您可以在那里看到巨大的差异。