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

据我了解，算法的复杂度是排序时执行的最大操作数。因此，冒泡排序的复杂度应该是算术级数（从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) ？

这是因为大 O 表示法描述了算法的本质。扩展中的主要术语(n-1) * (n-2) / 2 is n^2。又如n增加所有其他项变得微不足道。

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