为什么泡沫排序的时间复杂度最好的情况是O(n)

Question

根据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)

Answer 1

你的实施

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;
            }
        }
    }
}