2

私が理解しているように、アルゴリズムの複雑さは、並べ替え中に実行される操作の最大数です。したがって、バブル ソートの複雑さは、n^2 ではなく、算術進行 (1 から n-1 まで) の合計である必要があります。次の実装では、比較回数をカウントします。

public int[] sort(int[] a) {
    int operationsCount = 0;
    for (int i = 0; i < a.length; i++) {
        for(int j = i + 1; j < a.length; j++) {
            operationsCount++;
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    System.out.println(operationsCount);
    return a;
}

10 個の要素を持つ配列の出力は 45 なので、1 から 9 までの等差数列の合計です。

では、なぜバブル ソートの複雑さは S(n-1) ではなく n^2 なのでしょうか?

4

3 に答える 3

7

これは、big-O 表記がアルゴリズムの性質を表すためです。拡張の主項(n-1) * (n-2) / 2は ですn^2。そして、n増加するにつれて、他のすべての項は重要ではなくなります。

より正確に説明することは大歓迎ですが、すべての意図と目的のために、アルゴリズムは次の動作を示しますn^2。つまり、時間計算量を に対してグラフにするnと、放物線状の成長曲線が表示されます。

于 2013-02-12T23:08:22.607 に答える