为什么冒泡排序复杂度为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的算术级数之和.

那么为什么Bubble sort的复杂性是n ^ 2,而不是S(n-1)？

Answer 1

这是因为big-O表示法描述了算法的本质.扩张的主要任期(n-1) * (n-2) / 2是n^2.因此,n所有其他条款的增加都变得微不足道.

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