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) の解決には約 30 分かかる場合がありますが、神と征服の O(nlogn) アルゴリズムには数秒しかかかりません。(100 万 ^2) と (100 万 * log2(100 万)) の違いをすばやく確認する方法です。大きな違いが見られます。