algorithm - 冒泡排序算法分析

Question

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

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

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

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

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

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