k個のソートされたリストをmax要素で並べ替える

Question

kを単独でリンクしたリストをソートし、各リストの最後の要素（リストの最後）で並べ替えた場合（mergesort）、ビッグO（実行時間/時間の複雑さ） ？リスト1〜kのサイズがn_1〜n_kであると仮定します。私はO（k * log（MAX（n_1〜n_k）））を考えていましたが、どのように、なぜ私がその考え方に来たのかはわかりません。

Answer 1

各リストの最大要素を格納するメモリがO（k）単位であると仮定すると、ソートリスト自体をマージする時間、つまり要素をマージする時間はO（sum（N _i）+ k * log k）。

各リストの終わりまで正確に1回移動する必要があるため、最初の用語があります。その後、最大値でリストに「タグ付け」し、タグ付きリストに対してマージソートを実行できます。第2項は、マージソートを使用してk個のアイテムをソートすることに由来します。元のリストがソートされたという事実は無関係になります。とにかくリスト全体をトラバースする必要があるからです。

リストが変更可能な場合は、リストを逆順に並べ替えて並べ替えてから、逆に並べ替えることができるため、追加のストレージがなくてもタイミングの複雑さは変わりません。リストを逆にするには、O（sum（N _i））が必要なので、時間の複雑さは変わりません。