complexity-theory - 为什么冒泡排序的复杂度是 O(n^2)？

Question

据我了解，算法的复杂度是排序时执行的最大操作数。所以，冒泡排序的复杂度应该是算术级数(从 1 到 n-1)的和，而不是 n^2。以下实现计算比较次数:

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的等差数列之和。

那么为什么冒泡排序的复杂度是 n^2，而不是 S(n-1)？

Answer 1

这是因为大 O 表示法描述了算法的性质。 (n-1) * (n-2)/2 展开式中的主要术语是 n^2。因此，随着 n 的增加，所有其他项都变得无关紧要。

欢迎您更准确地描述它，但出于所有意图和目的，该算法表现出 行为 的顺序为 n^2。这意味着如果您根据 n 绘制时间复杂度图，您将看到一条抛物线增长曲线。