サイズnのkソート済み配列のマージの下限

Question

タイトルが示唆するように、サイズnのk個のソート済み配列をマージする下限の証明は何ですか？私は縛りがO（kn * log [k]）であることを知っていますが、これはどのように達成されましたか？私はデシジョンツリーを使ってp要素の配列をソートするのと比較しようとしましたが、このプルーフを実装する方法はわかりません。

Answer 1

これはかなり簡単に証明でき、マージソートの方法で考えることができます。

サイズの配列をマージソートするには、K * Nには、O（KN * log（K * N））が必要です。

しかし、我々は、配列のサイズはNは、それがソートされているときに我々が知っているように、葉サイズのに到達する必要はありません。簡単にするため、Kは2の累乗であると仮定します。

サイズNのリーフに到達するために何回何度掛けなければなりませんか？
K回！

可視化は、だからあなたは、各ステップのコストN Kをマージすること、ログ（K）のステップを持っている、とログ（K）のステップがあります。したがって、時間の複雑さは、O（NK（ログ（K））がある

証明：。
は、それが下限でないと仮定しますと、私たちはより良い達成できるその後のサイズの任意の未知の配列について我々はサイズNのサブアレイに達するまでN * K我々は2でそれを分割することができ、マージソートをサイズNのアレイの各々をNlog（N）内のすべてのアレイをK用時間と合計を* N * log（N）時間。

サイズがNのK配列をソートした後、サイズの大きい配列にマージする必要があります。N * K、O（NK *（log（K））より小さくしてください下限。

最後に、比較モデルでは不可能なN * K * log（N * K）より小さい複雑さのサイズN * Kの未知の配列をソートしました。
したがって、あなたはOよりも優れて達成することはできません（NK *（）（Kをログ） Kをマージ中には、サイズN.

Answer 2

可能な実装の配列をソート。
のペア(element, arrayIndex)を保存heap data structureを作成してみましょう。

1. 対応する配列インデックスを持つ各配列の最初の要素をこのヒープに追加します。各ステップで
2. 、ヒープから（最低）対p上部を取り外し、（それが空でない場合）、結果にp.elementを追加し、p.arrayIndexインデックスを持つ配列から次の要素とヒープにペア(next, p.arrayIndex)を挿入。

'next'要素をトラッキングするには、kのインデックス/ポインタ/イテレータを持つ配列が必要です。これは、対応する配列の次の要素を指しています。

、いつでもヒープのためinsert/removeオペレーションヒープ内で最もk要素がありますがO(log(k))複雑さを持つことになります。すべての要素がヒープから一度挿入され、削除されます。要素の数はn*kです。全体的な複雑さはO(n*k*log(k))です。

Answer 3

k個の配列のそれぞれから次の項目を格納するサイズkの最小ヒープを作成します。各ノードはまた、それがどのアレイから来たかを記憶する。ヒープからの分をfinal_sorted_arrayに追加し、値がヒープに来た配列の次の要素を追加してソートされた配列を作成します。

ヒープの最小eltを削除するとO（log k）になります。あなたはNK要素を合計していますので、NK回実行してください。最終結果：O（NK log k）。