冒泡排序算法分析

Question

通常 buublesort 的运行时间复杂度是 O(n^2) 但下面给出的算法有一个 while 循环和一个 for 循环 for 循环取决于 n 但 while 循环只是一个布尔值检查器。谁能告诉我如何计算该算法的运行时间？

bool done;
done = false;
while ( ! done )
{
done = true;
for ( i = 0 ; i < a.length-1 ; i ++ )
     {
     if ( a[i] > a[i+1] )
     {

// Swap a[i] and a[i+1]

    temp = a[i];
    a[i] = a[i+1];
    a[i+1] = temp;

    done = false;
  }
 }
}

Answer 1

算法的复杂性是它在最坏情况中的运行时间（"case"我指的是输入数据的整个无限序列，其长度不断增加） .很明显，bubblesort 只需要 O(n) 操作 "to sort" 已经排序的数组。但这不算。有一些数组（实际上是数组序列）需要 O(n^2) 操作。

P.S。有时更有趣的是算法是否通常在 O(n) 或类似的情况下工作。但是对于 bubblesort 甚至 "mean expected time" 是 O(0.5*n^2) 这仍然与 O(n^2).

相同

Answer 2

计算算法复杂度的方法有多种。最简单也不严格的就是找出最坏的情况，统计它的cycles/iterations个数。

如果源数组的排列方式相反，您的代码将不得不进行恰好 n^2 次比较。

所有更好的方法都需要一些严肃的数学知识：你必须做一些严格的证明。例如，证明所选案例确实是最坏的案例。

Answer 3

这种情况比具有两个 for 循环的算法要难得多，因为外循环的确切迭代次数不仅取决于 N，还取决于数据的特定排列。

如果数组最初是排序的，则根本不会有交换，外层循环将运行只有一次，复杂度 O(N)。

如果数组最初是反向排序的，则每次比较都会引起交换，并且外循环会执行 N 次，总复杂度为 O(N²)。

一般情况更难评估，因为它取决于被置换元素的数量。可以证明（通过一个重要的数学论证）对于随机无序的数组，平均复杂度保持 O(N²).

冒泡排序算法分析

Analysis of a Bubble-sort algorithm

algorithm

sorting

big-o

bubble-sort