算法的运行时间（大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)。有人能解释一下吗？

- Ravi Bisla

---

是的，这实际上是O(n^2)，这是冒泡排序的成本，你正在这里执行...你可以通过搜索算法的名称并进入第一个结果来找到这个信息。http://en.wikipedia.org/wiki/Bubble_sort - Benjamin Gruenbaum

我已经检查过了，但是在推导过程中有些疑惑，所以才发帖询问。 - Ravi Bisla

Answer 1

冒泡排序在最好的情况下时间复杂度为 O(n)，因为它可以接收一个已经排好序的列表。

你需要在第二个嵌套循环后检查是否进行了任何交换。如果没有进行交换，则该列表已经排序，不需要继续执行，所以可以退出循环。

对于已经排序的列表，你在这种情况下只需要迭代所有 n 个元素一次。

- user123

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保持为false，因此我们在一次迭代后就退出外部循环，这给冒泡排序带来了O(n)的复杂度。

- RYO

Answer 3

你可以使用Sigma符号来计算迭代的次数（循环中的内容是常数时间，因此不重要）：

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

在第一次遍历（外部循环）期间，如果没有进行交换，则这是一个决定性的信息，表明数组已经排序完成，此时覆盖所有情况是无意义的。

因此，外部循环只需要迭代一次，而内部循环会迭代n次：总共进行n + 1次迭代 ==> O(n)。

- Mohamed Ennahdi El Idrissi