Bubble-sort算法的分析

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

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

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

如果数组最初被反向排序，则每次比较都会导致交换，并且执行外部回路N次，总复杂度为O(N²)。

一般情况下更难以评估，因为它取决于替换元素的数量。人们可以显示（通过一个不平凡的数学论证），对于随机无序的数组，平均复杂性仍然是O(N²)。

Answer 2

复杂算法的是在其运行时间的最坏情况（用“的情况下”我的意思的输入数据的长度增加了整个无限序列）。很明显，bubblesort只需要O（n）操作“排序”已经排序的数组。但那不算数。有一些阵列（实际上是阵列的序列），它们需要O（n^2）操作。

P.S.有时候，算法是否为通常在O（n）等中起作用会更有趣。但即使“平均预期时间”是O（0.5 * n^2），它仍然与O（n^2）相同。

Answer 3

如何计算算法的复杂性有几种方法。最简单而不是最严格的是找到最坏的情况并计算它的周期数/迭代次数。

如果源数组是反之亦然，你的代码将不得不完成n^2比较。

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