algorithm - アルゴリズムの実行時間 (big O))

Question

このアルゴリズムの実行時間を計算していますか?

                              Cost      No Of Times

for(j=1;j<=n-1;j++){          c1       n(loop will run for n-1 times +1 for failed cond              

    for(i=0;i<=n-2;i++){      c2       n*(n-1) (n-1 from outer loop and n for inner 

        if(a[i]>a[i+1]){      c3       (n-1)*(n-1)

            Swap              c4       (n-1)*(n-1) {in worst case }
        }
    }

最悪の場合、 T(n)= c1*n + c2*(n-1) n + c3 (n-1)(n-1) + c4*(n-1)(n-1) O(n ^2)

最良の場合:

T(n)=c1*n + c2*(n-1) n + c3 (n-1)(n-1) O(n^2)。

しかし、実際には最良の場合、バブルソートの時間計算量は O(n) です。 誰でも説明できますか？

Answer 1

バブル ソートは、最良の場合でも O(n) 時間の複雑さを持ちます。これは、既にソートされたリストを渡すことができるためです。

2 番目のネストされたループの後にスワップを行ったかどうかを確認する必要があります。スワップが行われなかった場合、リストはソートされ、続行する必要がないため、ループを中断できます。

すでにソートされているリストの場合、この場合、n 個の要素すべてを 1 回繰り返します。