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 个元素一次。

Answer 2

您实现冒泡排序的算法是正确的，但效率不高，

// n 是元素的总数

do{  

  swp = false // swp checks whether or not any variable has been swapped  
                      in the inner loop  

         for(i=0;i<=n-2;i++){  

                  if(a[i]>a[i+1])

                  {
                        swap(a[i],a[i+1])

                        sw = true
                   }
        n = n-1             
    }while(sw == true && n>0)

swp 是一个变量，它检查内部循环中是否有任何交换，
如果没有任何交换，这意味着我们的数组已排序。

冒泡排序的最佳情况是当元素已经按升序排序时（在这种情况下）
，内部循环只运行一次但 if 条件（在内部循环中）从未满足并且swp保持为假，因此我们退出在一次迭代后从外循环开始，这给出了冒泡排序 O(n) 的复杂度。

Answer 3

您可以使用 Sigma 表示法计算迭代次数（循环内的内容无关紧要，因为它是恒定时间）：

具有最佳情况运行时间的冒泡排序实际上是这种排序算法的增强版本。

在第一次解析（外循环）时，如果没有进行交换，那是数组排序的决定性信息，覆盖所有情况是没有意义的。

因此，外部循环将迭代一次，而内部循环将迭代n次：即 n + 1 次迭代 ==> O(n)。