13

我根据ALGORITHMS 2.2书中使用的方法推导出了冒泡排序在最佳情况下的时间复杂度。但结果却是 O(n^2)。

这是我的推导，希望任何人都可以帮助我找出错误的地方：

public void bubbleSort(int arr[]) {
for(int i = 0, len = arr.length; i < len - 1; i++) {
    for(int j = 0; j < len - i - 1; j++) {
        if(arr[j + 1] < arr[j])
            swap(arr, j, j + 1);
    }
}

}

Statements                      cost    times
i = 0,len = arr.length          c1          1
i < len - 1                     c2          n
i++                             c3          n - 1
j = 0                           c4          n - 1
j < len - i - 1                 c5          t1(i=0) + t1(i=1) + ... + t1(i = n-2)
j++                             c6          t2(i=0) + t2(i=1) + ... + t2(i = n-2)
arr[j + 1] < arr[j]             c7          t3(i=0) + t3(i=1) + ... + t3(i = n-2)
swap(arr, j, j + 1)             c8          t4(i=0) + t4(i=1) + ... + t4(i = n-2)

T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5t5 + c6t6 + c7t7 + c8t8 = c1 + c2n + c3(n - 1) + c4(n - 1) + c5 [t1(i=0) + t1(i=1) + ... + t1(i = n-2)] + c6[t2(i=0) + t2(i=1) + ... + t2 (i = n-2)] + c7[t3(i=0) + t3(i=1) + ... + t3(i = n-2)] + c8[t4(i=0) + t4( i=1) + ... + t4(i = n-2)];

在最佳阵容中，序列在排序之前已经是正数。那么 t8 应该是 0。

T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5[t1(i=0) + t1(i=1) + ... + t1(i = n-2 )] + c6[t2(i=0) + t2(i=1) + ... + t2(i = n-2)] + c7[t3(i=0) + t3(i=1) + . .. + t3(i = n-2)]

时间复杂度为 O(n^2)

4

3 回答 3

30

您的实施

public void bubbleSort(int arr[]) {
    for(int i = 0, len = arr.length; i < len - 1; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j])
                swap(arr, j, j + 1);
        }
    }
}

无法控制内部循环中是否有任何交换，如果没有则退出外部循环。

这种控制使得最好的情况（一个已经排序的数组）可能是 O(n)，因为当它第一次运行时，内部循环中没有交换。

public void bubbleSort(int arr[]) {
    boolean swapped = true;
    for(int i = 0, len = arr.length; swapped && i < len - 1; i++) {
        swapped = false;
        for(int j = 0; j < len - i - 1; j++) {
            if(arr[j + 1] < arr[j]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
    }
}
于 2012-09-20T04:00:11.267 回答
1

冒泡排序的最佳情况是元素已经排序。

通常的实现给出了最佳、平均、最坏情况的 O(n^2) 时间复杂度。

我们可以通过在每次迭代时检查数组是否已排序（交换将指示未排序的数组）来修改冒泡排序。

一旦发现数组已排序（如果没有发生交换），控制就退出循环或循环继续执行直到长度为 1。

插入排序也是如此！

于 2018-05-09T19:03:06.257 回答
0

我不确定你在数什么。通常，当您谈论比较排序算法时，您应该计算进行的比较次数。冒泡排序就是这样认为的。在这种情况下，您提出的算法是 O(n^2)。

如果您计算交换次数，它的 O(1) 甚至可能会说 O(0)。然而，像这样分析冒泡排序是很少见的。

但是，您可以很容易地改进 Bubble 以在最佳情况下获得 O(N)。例如通过引入一个标志swap_was_made。如果它在内部结束时为假，for您可以完成。在最好的情况下，它将复杂性降低到 O(N)（一个内部 for 循环）。在公平均匀分布的情况下，它将预期或平均复杂度降低到 O(N^2/2) ......但请仔细检查我可能是错的。没有在这里做数学。

于 2012-09-20T04:02:29.400 回答