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) 呢？

4

3 回答 3

7

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

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

于 2013-02-12T23:08:22.607 回答
0

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

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

当您operationsCount在内循环中运行任何代码之前递增变量时，我们可以说我们之前分析中的 k（在内循环内执行的基本操作的数量）为 1。因此，求解Sum_{i=0}^{n-1}{n-i-1}给出n^2/2 - n/2，并将 n 替换为 10 给出最终结果为 45，与运行代码得到的结果相同。

于 2013-02-12T23:43:11.193 回答
0

最坏情况：表示给定任何大小为 n 的输入，算法执行的最长运行时间

所以我们将考虑这个最坏情况的完全倒退列表

int[] arr= new int[]{9,6,5,3,2};

Number of iteration or for loops required to completely sort it  = n-1 //n - number of elements in the list

1st iteration requires (n-1) swapping + 2nd iteration requires (n-2) swapping + ……….. + (n-1)th iteration requires (n-(n-1)) swapping

i.e. (n-1) + (n-2) + ……….. +1 = n/2(a+l) //sum of AP
=n/2((n-1)+1)=n^2/2

这么大的 O 表示法 = O(n^2)

于 2021-10-05T15:09:41.587 回答