1

次のアルゴリズムの基本的な操作を計算する方法を理解するのにいくつかの困難があります。

画像

ステップの計算はどういうわけか次のようになっていることを私は知っています:

(1)= 1ステップ:割り当て

(2)= 1ステップ:割り当て

(3)= 3+(n-1)ステップ:(n-1)回実行される3つの比較

(4)= 1ステップ:割り当て

(5)= 2+(n-2):(n-1)+(n-2)+ ... + 2 + 1 =(n-1)n/2回受ける割り当てと比較

(6)= 3ステップ:2つの配列、1つの比較[<]および1つの操作[-]

(7)= 4ステップ:2つの配列、1つの操作[-]、およびスワップへの関数呼び出しはステップ3 n(1)

(8)= 2ステップ:割り当てと加算の操作

最悪のシナリオは(n ^ 2 + n + 2n + 2)= O(n ^ 2)であると推測できます。これは、最悪の場合は、リストが最初の値を大きい値として、最後の値が大きい順に並べられているためです。 i = 0からn(i-1)までの合計として得られる最小値として。

また、リストがすでに注文されている場合の最良のシナリオ。これは、結果として、リストが一定の速度で実行されることを意味します。

私の問題は、アルゴリズムからプリミティブ演算を収集する方法を見つけることです。これにより、cとn_0を計算して、Ordoの定義でこれを自分で証明できます。

4

1 に答える 1

0

ソートアルゴリズムに特定の時間複雑性があると誰かが言うとき、彼らは通常、必要な比較の数を指します。すでに行ったように、要素間の比較の数を数え、定数を計算する必要があります。

于 2013-03-14T18:43:20.143 に答える