1

クローゼット ペア アルゴリズムの n log^2 n 時間から n log n 時間に移行する方法を理解しようとしています。以下の部分を取得します（http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.htmlから）

  1. セットを行 l で 2 つの等しいサイズの部分に分割し、各部分の最小距離を再帰的に計算します。
  2. d を 2 つの最小距離の最小値とします。
  3. l から d より遠くにある点を削除する
  4. 残りのポイントを y 座標に従って並べ替えます
  5. 残りの点を y 順にスキャンし、各点から 5 つの近傍点までの距離を計算します。
  6. これらの距離のいずれかが d 未満の場合、d を更新します。

ステップ 4 は、O(n log n) 時間かかるソートであり、他のすべてのステップを支配します。これは、アルゴリズム全体が O(n log n) 時間を達成するために O(n) に減らす必要があるものです。 . そして、これは私が理解するのに苦労している部分です。著者が提案する

ステップ 1: セットを ... に分割し、各部分の距離を再帰的に計算し、各セットのポイントを y 座標でソートされた順序で返します。ステップ 4: 2 つのソート済みリストを O(n) 時間で 1 つのソート済みリストにマージします。

O(n log n) 時間かかる再帰ステップで、y 座標でポイントを並べ替える必要があります。どうすればこれを回避できますか? マージは O(n) ですが、まだどこかでソートする必要があります。

4

3 に答える 3

1

O( n  log  n ) が問題である理由は、それを何度も何度も繰り返しているからです: セットを 2 つのサブセットに分割し、それらのそれぞれを 2 つのサブセットに分割すると、7 つのソート (1 つ以上) が必要になります。セット全体、半分に 2 つ、4 分の 1 に 4 つ）。

したがって、提案では、以前のソートの結果を再利用することでこれを修正します。したがって、最小のパーティション (それぞれが O(1)、合計 O( n ))の完全なマージソートを行いますが、より大きなパーティションについては、単に行う必要があります。それらの結果を結合する単一の O( n ) マージ パス。したがって、O( n  log  n ) の価格は合計で 1 回しか支払われません。これで問題ありません。

于 2016-12-30T22:58:18.187 に答える