为什么冒泡排序的最佳情况的时间复杂度是O（n） [英] why is the time complexity of bubble sort's best case being O(n)

问题描述

我根据《 算法》 2.2中使用的方法推论出气泡排序的时间复杂度。但是答案却是O（n ^ 2）。

I deduced the time complexity of bubble sort in its best case according to the mothod used in book ALGORITHMS 2.2. But the answer turned out to be O(n^2).

这是我的推导，希望有人能帮助我找出问题所在：

Here's my derivation, hope anyone can help me find out where is wrong:

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）];

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。

in its best cast, the sequence is already positive before sorting. Then t8 sould be 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）]

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）

The time complexity is 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);
        }
    }
}

缺少控制是否

该控件使最好的情况（一个已经排序的数组）成为可能。 ）是O（n），因为从那以后第一次运行时，内部循环中就没有交换。

That control makes it possible that the best case (an already sorted array) is O(n), since then there are no swaps in the inner loop when it runs the first time.

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

这篇关于为什么冒泡排序的最佳情况的时间复杂度是O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！