n 個の要素 [1,...,n] を持つ配列の最大要素 M が与えられた場合、すべての比較ベースの並べ替えアルゴリズムの時間計算量の下限 Ω(nlogn) はどのように影響を受けますか? 配列の最大要素 M が与えられていることを強調しなければなりません。
2 に答える
3
影響はありません。
n!可能な順列があり、各比較 OP には 2 つの可能な結果 (「左が高い」または「右が高い」)
があることに注意してください。
比較ベースのアルゴリズムでは、それぞれの「決定」は 1 つの比較の結果に従って行われます。
したがって、順列の正しい順序を正しく決定するには、(最悪の場合) log 2 (n!) 回の比較が必要になります。
ただし、log 2 (n!) が Theta(nlogn) にあることはよく知られています。手元の範囲に関係なく、Omega(nlogn) の下限に戻ります。
整数をより効率的にソートするために、比較のみを使用しない他の方法が存在することに注意してください。
于 2013-12-24T17:01:29.250 に答える
1
Mが配列の要素の絶対値の境界であり、要素が整数である場合、別の配列を に初期化したままにして、元の配列をスキャンし、それぞれの出現回数をカウントすることで、配列を時間内に並べ替えることO(n + M)がint occurrences[2M + 1];でき0ます要素を使用して出力配列を書き込みますoccurrences。
要素が浮動小数点数 (正式には実数) の場合、それらの大きさに制限があっても効果はありません。
要素が整数であり、負になる可能性がある場合 (正式には、任意の大きさの整数)、大きさに上限があっても効果はありません。
編集：O(n)最初の段落にありましたO(n + M)。
于 2013-12-24T17:02:59.403 に答える