質問は次のようになります： 長さn/kのk個のソートされたリストがあります（kはnを分けると仮定します）。 これらのリストを実行時間の複雑さO（k + nlogk）の長さn の1つのリストにマージするアルゴリズムを見つける必要があります。ソートされたリストをマージするアルゴリズムを見つける
私はカップルでリストをマージすることを考えていましたが、 より、マージされたリストを再びカップルでマージするのではなく、そうすることで長さnのソートされたリストを取得します。
私のアルゴリズムの時間計算量を計算すると、必要な時間よりもバッターであるO（nlogk）が得られました。
私の方法が間違っているのだろうかと思っていました。 助けてくれてありがとう！
私の理解するには、次のような考え方で
O(k^2*(n/k)) = O(kn)
の運転時間を達成することが可能です。リストが非減少順にソートされているとします。すべてのリストが空になるまで繰り返します。各反復で、kの手順を使用して、リストの最初の要素すべてに対して、最初の要素が最小であるリストを決定します。リストから要素を削除し、結果に追加します。
しかし、O（nk）は必要なO（k + nlogk）以上です。 –
あなたのやり方は問題ありません。
k < = nかつk> = 1とすると、O（n log k）= O（k + n log k）となる。これらの両方は、「kはnを分けると仮定している」という声明によって暗示されているので、あなたの結果は想定されているものです。
これらの条件を緩和すると、k> nの場合を考慮する必要があり、それらのkリストの一部は空のです。その後、空のリストをすべてマージするのにかかる時間を心配する必要があり、アルゴリズムではO（k + n log k）時間がかかります。
@MattTimernansで述べたように、k < = nなので、O（nlogk）はO（k + nlogk）であることが分かります。ヒープを使ってO（k + nlogk）を得るのは簡単です。最初に、O（k）を取る各リストのすべての最初の要素のヒープを構築します。次に、要素をポップし、新しい要素をヒープに戻します。 O（k + nlogk）
のリストをすべてマージしてソートリストを作成します。 –
各反復では、リストをマージするためにO（n）が必要であり、ログkの反復があります。 @ KarolyHorvath – Liad
k <= n（常にそうである）と仮定すると、複雑さはO（nlogk） –