ソートされていない2つの配列があります。それらを個別にソートしてからマージした方が速いでしょうか? それとも、最初に配列を連結し、結合された巨大な配列をソートする方が速いでしょうか?
質問する
579 次
5 に答える
7
O(1)連結が で行われ、テイクのマージO(n)とソートが行われると仮定するとO(n log n)、次のいずれかを選択できます。
- 並べ替えとマージ:
O(n log n) + O(n) = O(n log n) - 連結して並べ替える:
O(1) + O((2n) log (2n)) = O(n log n)
したがって、漸近的に両方のオプションは同等です。
もちろん、MergeSort を使用する場合、議論全体はとにかく意味がありません。
于 2013-04-10T11:35:10.713 に答える
4
明らかに、big-O はこの問題について何も言っていません。使用しているアルゴリズムがクイックソートであると仮定します。平均実行時間は次のとおりです。
したがって、並べ替えてからマージすると、次のようになります。
f1 = 1.39n * ログ (n) * 2 + 2n
マージしてから並べ替える:
f2 = n + 1.39 * 2n * ログ (2n)
違いは
f2 - f1 = -n + 2.78n > 0
一般的なケースでは、ソート アルゴリズムが複雑な場合
C = k * nlog(n)
k は通常 1 より大きくなければならず、0.5 に近くなる可能性は低いため、マージのコストが最大で 2n であると想定している場合は、ソートしてからマージする方が高速になります。
于 2013-04-10T13:42:58.300 に答える
0
それは、並べ替えアルゴリズムとデータのサイズに依存すると思います。
しかし、大まかな推測では、ロット全体をマージしてからソートする方が望ましいということです。その場合のマージは単なる追加であるためです。
それ以外の場合は、並べ替えマージを適用する必要があります。
于 2013-04-10T11:32:24.257 に答える
0
それは、使用しているテクニックによって異なります。
最初に並べ替えてからマージすると、最新のマルチプロセッサ アーキテクチャでより良い結果が得られます。この場合、両方の配列で並べ替えアルゴリズムを並列スレッドで実行しO(nlogn)(ただし、定数ははるかに少なくなります)、O(n)時間内にそれらをマージできます。
于 2013-04-10T11:35:04.450 に答える
0
2 番目の配列のすべてのエントリが 1 番目の配列のすべてのエントリよりも大きいことが保証されている場合は、それぞれを並べ替えた後に配列を連結できます。すべてのソート アルゴリズムには線形よりも複雑な複雑性があるため、ソート タスクを個別にソートできるサブセットに分割できる場合は、それを実行する必要があります。
しかし、配列をマージした後にエントリを再度ソートする必要がある場合、事前に各配列をソートしても、これ以上速くなることはほとんどありません。
正確に知りたい場合は、大量のテスト データを作成し、自分でパフォーマンスを測定します。
于 2013-04-10T11:34:21.667 に答える