最も近い点のペア（CLRS pg 1043）：ソートされた配列を2つのソートされた配列に分割する実行時間

Question

O（nlgn）時間内に最も近い点のペアを見つけると、ソートされたリストを2つのソートされたリストCLRS 3rd ed pg 1043）はO（n）時間に実行されると言われています。

しかし、これは、その行に私は（私はそれを与えて、バイナリツリーとして保存した場合、それはO（LGN）の時間で実行すると仮定したいと考えているのは難しい見つける一定の時間内に4つのランを、前提としていO（nlgn）の合計実行時間

Yは並べ替えられた配列で、YLとYRは2つの新しいサブ配列ですPLはランダムな順序でYのサブセットですが、YLは同じサブセットですが

ここで私の推論は間違っていますか？

Answer 1

簡潔にするため、ここではリストが整数であり、文字列や整数ではなく、ここで大きく複雑になると仮定しています。

forループ

1. ：ここで考慮すべき2回の計算があります

   これはNが

2. がここにトリッキーな部分である私は仮定していた、Y時間の長さのために走る - Yの比較[i]がPL（注：2つの数値の比較は、ワードサイズであるとみなすと一定です）。今、私たちがランダムアクセスマシンを扱っているので、Y [i]にアクセスすることは一定です。しかし、それを長さの配列PLと比較するには、kはk時間かかるでしょう。このkが非常に小さく、入力配列Yのサイズに依存しない場合、これは理想的には一定になります。

これをより正確に書くと、kの比較に要する時間（PLの長さ）が考慮されるため、この擬似コードの合計時間はO（Nk）になります。しかし、kが無作為でNに無関係であるという仮定が真であれば、それは実際にはO（N）

Answer 2

私はそれが本書ではうまくいくはずですが、以下のように、次のアイデアを思い付くことができます。

• Y[i]、X[i]、YL[i]、XL[i]、YR[i]とXR[i]は番目の点（iのインデックスに対応する、整数であるので、あなただけのいくつかのグローバルを保存する必要がインデックスを指定すると、xまたはy座標が返されます）。
• PL[i]は、i番目の点が左側にある場合はtrue、それ以外の場合はfalseです。各再帰ステップで

は、あなたがPL[i]使用y座標（O(n)時間）を計算することができます。次に、本のアルゴリズムを使用して、2つのセット "左"と "右"のセットを分離し、（このアクセスはO(1)なので、全体としてO(n)となります）のif Y[i] in PLを置き換えます。

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

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