K個のN個の要素の並べ替えられた配列がある場合、k個の並べ替え済み配列をマージする - 2つの解を比較する
[0, 1, 2]
[1, 6, 8]
[10, 11, 12]
私はその後、O（KNの*ログ（KN）の各時間を最小に取り戻す、リストとそのすべての要素を循環し、ヒープにそれらを挿入することによって、それらをマージするヒープを使用することができることを知っています）。
私はインターネット上でチェックし、もう1つの一般的な解決策は、K個の要素だけの最小ヒープを使用し、ヒープにKリストのすべての最初の項目を挿入し、次に最小値を取得して、その最小要素を所有していた。
より効率的なメモリ要件（2番目のケースではO（K））とは別に、2番目の方法は時間的に効率的ですか？
オプションのボーナスポイント：上記よりもさらに優れたアルゴリズムがありますか？
各要素（N * K）に対してheapify（log（K））操作を実行するので、2番目のバージョンのランタイムはO（KN * log（K））にする必要があります。そう、それはより速いです。私はこの問題を解決するより効率的な方法を考えることはできません。
すべての入力リストの並べ替えを実行するのに十分なメモリがある場合、最初の方法は問題ありませんが、すでにソートされたリスト間でk方向のマージを実行するだけで簡単です各入力リストにあるインデックスを追跡する余分なスペース（K要素のリスト）。これはO(K^2 * N)ソリューションです。
最初の方法またはk-wayマージはどちらかというとKがNと比べてどれほど大きいかによって決まり、最初の方法のヒープを構築するコストは忘れないようにしてください。アイデアを伝える：
k=5; n=100
k*n*log(k*n)
=> 3107
k*k*n
=> 2500
k=100; n=100
k*n*log(k*n)
=> 92103
k*k*n
=> 1000000
2番目の方法ではメモリが少なくて済みます。これは非常に重要です。入力リストがメモリに収まらないときに行く方法です - したがって、各リストから1つの要素を取り出し、ヒープに配置し、次の結果を決定し、出力に書き出しますそれに応じてヒープを更新します。つまり、複雑さはO(KN * log(K))です。
k=5; n=100
k*n*log(k)
=> 804
k=100; n=100
k*n*log(k)
=> 46051
ボトムライン：再び、アイデアを与えるために、入力がメモリに収まるとkが小さく、など@btilly指摘し、第2の方法は、ときに、第1の方法の代わりにマージK-方法を使用し理論的にはそれらすべての中で最高ですが、実用的な考慮はk-wayをより速くマージさせるかもしれません。いつものように、最良の戦略は、いくつかの実際のデータでプロファイルを作成し、勝者を選ぶことです！
最初の回答はO(KN * log(KN))です。第2の回答はO(KN * log(K))です。一般的にはそれ以上のことはできません。
つまり、実際には改善することがあります。最小要素をヒープにダンプするのではなく、merge-sortのようなマージのツリーを作成します。次に、ロジックを追加します。マージの片側を引っ張っているように見えるときは、先に飛び降りてランを探してみてください。
Kが大きく、比較が高価で、データに多くの実行がある場合、勝利は重要になります。
ソートアルゴリズムの例としては、このようなことを試してみて、実世界の多くのユースケースに対してきめ細かくチューニングされている例については、https://en.wikipedia.org/wiki/Timsortを参照してください。
お返事ありがとうございます！ k-wayマージが遅くなることはありませんか？あなたは常に各段階でK比較を行う必要があるでしょう（部分的にソートされたヒープツリーとの比較が少ない） – Dean
O（KN）ソリューションを説明できますか？ 私はあなたのことを理解していないかもしれませんが、次の要素を選択するとO（K）時間かかるので、O（K^2 * N）の解決策になります。 – alper
@alperあなたが正しいです、私は次の要素を選ぶコストを考慮していませんでした：/私は私の答えを更新します。しかし、とにかくヒープを使用した場合、それを構築するためのO（KN）コストも支払わなければなりません。結局のところ、最善の選択肢は、K –