algorithm - 算法的运行时间(大O))

Question

我正在计算这个算法的运行时间？

                              Cost      No Of Times

for(j=1;j<=n-1;j++){          c1       n(loop will run for n-1 times +1 for failed cond              

    for(i=0;i<=n-2;i++){      c2       n*(n-1) (n-1 from outer loop and n for inner 

        if(a[i]>a[i+1]){      c3       (n-1)*(n-1)

            Swap              c4       (n-1)*(n-1) {in worst case }
        }
    }

在最坏的情况下T(n)= c1*n + c2*(n-1)n + c3(n-1)(n-1) + c4*(n-1)(n-1) 这是 O(n^2)

在最好的情况下:

T(n)=c1*n + c2*(n-1)n + c3(n-1)(n-1)这是 O(n^2)。

但实际上在最好的情况下冒泡排序的时间复杂度为 O(n)。谁能解释一下？

Answer 1

冒泡排序在最好的情况下具有 O(n) 的时间复杂度，因为可以将已排序的列表传递给它。

您必须检查在第二个嵌套循环之后是否进行了任何交换。如果没有进行交换，则列表已排序且无需继续，因此您可以打破循环。

对于一个已经排序的列表，在这种情况下，您将对所有 n 个元素进行一次迭代。