このアルゴリズムの効率は何ですか

Question

次のアルゴリズムの大きなO値は何ですか？それはなぜその価値ですか？

algorithm A (val array <ptr to int>) 
    1 n = 0 
    2 loop (n < array size) 
    1 min = n; 
    2 m = n; 
    3 loop (m < array size) 
     1 if (array[m] < array[min]) 
      1 min = m; 
    4 swap(array[min],array[n]); 
    3 n = n + 1 

私はO（n^2）と答えましたか？この結論にどのように到達したかについては、内側ループはn回（nは配列サイズ、nは配列サイズ）のn回実行する。n * n = n^2

Answer 1

はい！あなたは正しいです！

これは選択ソートアルゴリズムです。 より正確にはΘ（n^2）です。

編集：なぜその値ですか？

あなたは最初の要素を使用します。それを他のすべての要素と比較して、配列内の最小値を見つけ出し、最初に配置します。反復：n。 2番目の要素を取ります。それを残りの配列と比較し、その部分の最小値（配列全体の2番目の最小値）を見つけて2番目の場所に配置します。反復：n-1。 最後の要素についてこのように続き、反復：1。

合計= n + n-1 + ... +1 = n（n + 1）/ 2。それはO（n^2）です。

Answer 2

これは、 Selection sortと呼ばれ、実際にはO（n ）の複雑さを持っています。