小编Wen*_*ang的帖子

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