マージ ソートに詳しい方のために、サイズ n/2 の 2 つのサブ配列をマージするために必要な比較の最小数を計算しようとしています。ここで、n は元のソートされていない配列内の項目の数です。
アルゴリズムの平均および最悪の場合の時間の複雑さは O(nlogn) であることはわかっていますが、必要な比較の正確な最小数 (n に関して) はわかりません。
質問する
9508 次
3 に答える
7
リストの 1 つが完全にトラバースされた後の正常な実装を想定すると、マージ ステップの比較の最小数はおよそn/2(ちなみにまだ です) です。O(n)
たとえば、事実上すでにソートされている 2 つのリストがマージされている場合、大きい方のリストの最初のメンバーは、n/2使い果たされるまで小さい方のリストと何度も比較されます。その後、さらに比較することなく、より大きなリストをコピーできます。
List 1 List 2 Merged List Last Comparison
[1, 2, 3] [4, 5, 6] [] N/A
[2, 3] [4, 5, 6] [1] 1 < 4
[3] [4, 5, 6] [1, 2] 2 < 4
[] [4, 5, 6] [1, 2, 3] 3 < 4
[] [5, 6] [1, 2, 3, 4] N/A
[] [6] [1, 2, 3, 4, 5] N/A
[] [] [1, 2, 3, 4, 5, 6] N/A
リストには 6 つのメンバーがあり、3 つの比較が行われたことに注意してください。
O(n)繰り返しますが、最良の場合でもマージ手順は効果的に考慮されることに注意してください。O(n*lg(n))マージステップがO(n)リスト全体にまたがり、分割/マージがO(lg(n))再帰のレベルで発生するため、マージソートアルゴリズムには時間の複雑さが伴います。
于 2012-04-20T15:42:58.257 に答える
4
この答えは、いくつかのランダウ記号を使用して記述された漸近的な動作だけでなく、正確な結果を提供します。
長さmとnのリストをマージするには、少なくとも min( m , n ) の比較が必要です。その理由は、入力リストの 1 つが完全に処理された場合にのみ要素の比較を停止できるためです。つまり、少なくとも 2 つのリストの小さい方を反復処理する必要があります。この数の比較は、一部の入力に対してのみ十分であることに注意してください。そのため、可能な入力データの最良のケースを想定しているという意味では最小限です。最悪の場合の入力では、より高い数値、つまりn ⌈lg n⌉ − 2⌈lg n⌉ + 1が見つかります。
n = 2 kを2の累乗とします。iをマージ レベルとし、0 ≤ i < kとします。レベルiでは、2 k − i − 1 回のマージを実行し、それぞれに 2 i回の比較が必要です。これら 2 つの数値を乗算すると、2 k − 1 回の比較が得られます。これはn /2 に等しくなります。kレベルのマージを合計すると、nk /2 = ( n lg n )/2 の比較が得られます。
ここで、 nを 2 のべき乗よりも 1 小さいとします。k = ⌈lg n ⌉ が依然としてマージ レベルの数を表すとします。2kの場合と比較すると、各レベルでの比較が 1 つ少なくなります。したがって、マージの総数はkだけ減少し、結果として 2 k k /2 − k = (2 k /2 − 1) k回の比較が行われます。ただし、もう 1 つの要素を削除してn = 2 k − 2 になると、最上位のマージの数は減りません。これは、他のリストがすでに短いリストであるためです。これは、この辺りで事態がより困難になる可能性があることを示唆しています。
それでは、以前の結果を確認し、他の値の比較回数を計算するために使用できる小さなデモ プログラムを作成してみましょう。
mc = [0, 0] # dynamic programming, cache previous results
k = 1 # ceil(lg n) in the loop
for n in range(2, 128):
a = n // 2 # split list near center
b = n - a # compute length of other half list
mc.append(mc[a] + mc[b] + min(a, b)) # need to sort these and then merge
if (n & (n - 1)) == 0: # if n is a power of two
assert mc[-1] == n*k/2 # check previous result
k += 1 # increment k = ceil(lg n)
print(', '.join(str(m) for m in mc)) # print sequence of comparison counts, starting at n = 0
これにより、次のシーケンスが得られます。
0, 0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35,
37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85,
88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133,
136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186, 192,
193, 195, 197, 200, 202, 205, 208, 212, 214, 217, 220, 224, 227, 231,
235, 240, 242, 245, 248, 252, 255, 259, 263, 268, 271, 275, 279, 284,
288, 293, 298, 304, 306, 309, 312, 316, 319, 323, 327, 332, 335, 339,
343, 348, 352, 357, 362, 368, 371, 375, 379, 384, 388, 393, 398, 404,
408, 413, 418, 424, 429, 435, 441
オンライン エンサイクロペディア オブ 整数シーケンスで調べると、このシーケンスが 0, ..., n の 2 進展開で 1 の総数を表していることがわかります。そこにもいくつかの式がありますが、それらは不正確である (いくつかのランダウ記号項を含む) か、他の重要なシーケンスに依存しているか、かなり複雑です。私が最も気に入っているものは、上記の私のプログラムが行ったことを表現しています。
a(0) = 0、a(2n) = a(n)+a(n-1)+n、a(2n+1) = 2a(n)+n+1。- Ralf Stephan、2003 年 9 月 13 日
これらの代替案を考えると、上記のスクリプトを使用してこれらの数値を計算すると思います。アサーションとこれに関連するすべてのものを削除し、その事実に依存し、a < bこれをより大きなプログラムに含める場合は出力も削除できます。結果は次のようになります。
mc = [0, 0]
for n in range(2, 1024):
a = n // 2
mc.append(mc[a] + mc[n - a] + a)
たとえば、n = 3 の場合、2 つの比較しか得られないことに注意してください。明らかに、これは両方の極値要素を中央値の要素と比較する場合にのみ機能するため、極値要素を互いに比較する必要はありません。これは、上記の計算が最良の入力に対してのみ機能する理由を示しています。最悪の場合の入力では、ある時点で最小要素と最大要素を相互に計算し、そのn ⌈lg n⌉ − 2⌈lg n⌉ + 1式によって計算される 3 つの比較につながります。
于 2012-09-10T13:37:26.613 に答える
-1
比較ごとに、2 つのリストのいずれかから 1 つの要素を排出します。したがって、比較の数は、最大で 2 つのリストの長さの合計になります。示されているようPlatinumに、1 つの配列の最後に到達し、もう 1 つの配列にまだアイテムが含まれている場合、それは少なくなる可能性があります。
したがって、比較回数は と の間n/2ですn。
于 2012-04-20T15:54:06.867 に答える