13

本ALGORITHMS2.2で使用されている方法に従って、最良の場合のバブルソートの時間計算量を推定しました。しかし、答えはO（n ^ 2）であることが判明しました。

これが私の派生です、誰かが私がどこが間違っているかを見つけるのを手伝ってくれることを願っています：

public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
    for(int j = 0; j < len - i - 1; j++) {
        if(arr[j + 1] < arr[j])
            swap(arr, j, j + 1);
    }
}

}

Statements                      cost    times
i = 0,len = arr.length          c1          1
i < len - 1                     c2          n
i++                             c3          n - 1
j = 0                           c4          n - 1
j < len - i - 1                 c5          t1(i=0) + t1(i=1) + ... + t1(i = n-2)
j++                             c6          t2(i=0) + t2(i=1) + ... + t2(i = n-2)
arr[j + 1] < arr[j]             c7          t3(i=0) + t3(i=1) + ... + t3(i = n-2)
swap(arr, j, j + 1)             c8          t4(i=0) + t4(i=1) + ... + t4(i = n-2)

T（n）= c1 + c2n + c3（n-1）+ c4（n-1）+ c5t5 + c6t6 + c7t7 + c8t8 = c1 + c2n + c3（n-1）+ c4（n-1）+ c5 [t1（i = 0）+ t1（i = 1）+ ... + t1（i = n-2）] + c6 [t2（i = 0）+ t2（i = 1）+ ... + t2 （i = n-2）] + c7 [t3（i = 0）+ t3（i = 1）+ ... + t3（i = n-2）] + c8 [t4（i = 0）+ t4（ i = 1）+ ... + t4（i = n-2）];

最良のキャストでは、シーケンスはソート前にすでに正です。その場合、t8は0になります。

T（n）= c1 + c2n + c3（n-1）+ c4（n-1）+ c5 [t1（i = 0）+ t1（i = 1）+ ... + t1（i = n-2 ）] + c6 [t2（i = 0）+ t2（i = 1）+ ... + t2（i = n-2）] + c7 [t3（i = 0）+ t3（i = 1）+。 .. + t3（i = n-2）]

時間計算量はO（n ^ 2）です

4

3 に答える 3

30

あなたの実装

public void bubbleSort(int arr[]) {
    for(int i = 0, len = arr.length; i < len - 1; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j])
                swap(arr, j, j + 1);
        }
    }
}

内側のループにスワップがあったかどうかの制御が不足しており、スワップがなかった場合は外側のループから抜け出します。

この制御により、最良のケース（すでにソートされた配列）がO（n）である可能性があります。これは、最初に実行するときに内部ループにスワップがないためです。

public void bubbleSort(int arr[]) {
    boolean swapped = true;
    for(int i = 0, len = arr.length; swapped && i < len - 1; i++) {
        swapped = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}
于 2012-09-20T04:00:11.267 に答える
1

バブルソートの最良のケースは、要素がすでにソートされている場合です。

通常の実装では、最良、平均、最悪の場合にO（n ^ 2）の時間計算量が与えられます。

反復ごとに配列がソートされているかどうか（スワップはソートされていない配列を示します）をチェックすることで、バブルソートを変更できます。

配列がソートされていることが判明すると（スワップが発生しない場合）、制御はループを終了するか、ループは長さ1まで実行を継続します。

そして、挿入ソートについても同じことが言えます！

于 2018-05-09T19:03:06.257 に答える
0

何を数えているのかわかりません。一般に、比較ソートアルゴリズムについて話しているときは、行われた比較の数を数える必要があります。バブルソートはそのように見なされます。この場合、提示したアルゴリズムはO（n ^ 2）です。

スワップの数を数えると、そのO（1）、または1つでもO（0）と言うことができます。ただし、そのようなバブルソートを分析することはまれです。

ただし、Bubbleを非常に簡単に改善して、最良の場合にO（N）を取得できます。たとえば、フラグを導入しswap_was_madeます。インナーの終わりにfalseがあれば、終了forできます。最良の場合、複雑さをO（N）（1つの内側のforループ）に削減します。公平に均等に分散されている場合は、予想または平均の複雑さがO（N ^ 2/2）に削減されます...しかし、私が間違っている可能性があることを再確認してください。ここで数学をしませんでした。

于 2012-09-20T04:02:29.400 に答える