1

O(nlgn) 時間で最も近いポイントのペアを見つける際に、ソート済みリストを 2 つのソート済みリストに分割するための疑似コード (CLRS 3rd ed pg 1043) は、O(n) 時間で実行されると言われています。

CLRS pg 1043 のアルゴリズム

ただし、これは4行目が一定時間で実行されることを前提としていますが、これは信じがたいことです（バイナリツリーとして保存されている場合、O（lgn）時間で実行され、合計実行時間はO（nlgn）になります） .

Y はソートされた配列で、YL と YR は 2 つの新しいサブ配列です。PL はランダムな順序の Y のサブセットであり、YL は同じサブセットですが、ソートされた順序です。

私の推論のどこが間違っているのでしょうか?

4

2 に答える 2

1

簡単にするために、リストは整数であり、ここで非常に複雑になる可能性のある文字列や整数ではないと仮定しています。

ここで考慮すべき 2 つの計算があります。

  1. for ループ: これは Y 回実行されます。ここでは N であると想定しています。
  2. トリッキーな部分 - Y[i] と PL の比較 (注: 2 つの数値の比較は、2 つの数値がワード サイズであると見なす場合、一定です)。ここでは、ランダム アクセス マシンを扱っているため、Y[i] へのアクセスは一定です。ただし、長さの配列 PL と比較するには、たとえば k は k 時間かかります。この k が非常に小さく、入力配列 Y のサイズに依存しない場合、これは理想的には定数になります。

より高い精度で記述すると、k 回の比較にかかる時間 (PL の長さ) を考慮することになるため、この疑似コードの合計時間は O(Nk) になります。しかし、k がランダムであり、N に依存しないという仮定が成り立つ場合、それは実際には O(N) です。

于 2016-12-26T06:19:43.707 に答える
0

本ではどのように機能するのかわかりませんが、アルゴリズムがどのように見えるかを考えると、次のアイデアを思いつくことができます:

  • Y[i]、X[i]、YL[i]、XL[i]、YR[i]およびXR[i]は整数であり、th-point のインデックスに対応します (したがって、インデックスを指定すると、または座標iを返すグローバル配列を格納する必要があります)。xy
  • PL[i]- 番目のポイントが左部分にあるtrue場合はブール値、そうでない場合はブール値です。ifalse

各再帰ステップで、座標 ( time )PL[i]を使用して計算できます。次に、本のアルゴリズムを使用して、ポイントのセットを「左」と「右」の 2 つのセットに分離し、線を次のように置き換えます (このようなアクセスはであるため、全体としては になります)。yO(n)if Y[i] in PLif PL[Y[i]]O(1)O(n)

これにはO(n)時間の複雑さがあり、O(n)メモリを使用します。

したがって、最も近いペアの問題は、 でそのように解決されT(n) = O(n log n)ます。

于 2016-12-26T13:22:17.173 に答える