为什么冒泡排序复杂度为O（n ^ 2）？(Why Bubble sort complexity is

据我了解，该算法的复杂度，同时进行排序操作的最大数量。 因此，冒泡排序的复杂性应arithmmetic级数的总和（从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 ，你会看到一个抛物线增长曲线。

Answer 2:

让我们做一个最坏情况分析。

在最坏的情况下， if (a[i] > a[j])测试将总是为真，所以下一个代码3线将在每个循环步骤来执行。 内环从j变为= I + 1到n-1，所以它会执行Sum_{j=i+1}^{n-1}{k}初等运算（其中，k是涉及的操作的恒定数创建的temp变量，数组索引，和值复制）。 如果解决的总和，它给出了一些基本的操作等于k(ni-1) 外部循环将重复此k(ni-1)初等运算从i = 0到i = N-1（即。 Sum_{i=0}^{n-1}{k(ni-1)} ）。 所以，再一次，如果你解决你总和看到，基本操作的最终数目是正比于N ^ 2。 该算法是在最坏的情况下二次。

当你正在增加变量operationsCount在内部循环运行任何代码之前，我们可以说，K的我们前面的分析（内环内执行基本操作的次数）是1。所以，解决Sum_{i=0}^{n-1}{ni-1}给出n^2/2 - n/2 ，并用10代以n给出45°的最终结果，只是通过运行代码得到了相同的结果。

文章来源: Why Bubble sort complexity is O(n^2)?