评估给定Bubblesort算法的平均时间复杂性。

Question

考虑到Bubblesort的这个伪代码：

FOR i := 0 TO arraylength(list) STEP 1  
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

我要牢记的基本想法是什么来评估平均时间复杂性？我已经完成了计算最坏和最佳案例的计算，但是我被困在审议如何评估内部循环的平均复杂性以形成方程式的情况下被困。

最坏的情况是：

$$ sum_ {i = 0}^n left（ sum_ {j = 0}^{n - （i + 1）} o（1） + O（1） + O（1） right）= o（ frac {n ^2} {2} + frac {n} {2}）= o（n^2）$$

其中内部sigma代表内部环，外部sigma表示外环。我认为我需要由于“ If-then-break”的规定而更改两个Sigmas，这可能会影响外部Sigma，也可能会影响内部循环中的if-Clause，这将影响循环中所做的动作（4个动作 + 1比较，如果是的，则只有1个比较）。

为了澄清平均时间：此排序算法在不同列表（相同长度）上需要不同的时间，因为该算法可能需要或多或少地通过循环中/内部的步骤，直到列表完全按顺序排列为止。我试图找到一种评估所需这些回合平均值的数学（非统计方式）。

为此，我希望任何订单都具有相同的可能性。

Answer 1

对于长度$ n $的列表，平均值通常意味着您必须从所有$ n！$排列的[$ 1 $，..，$ n $]的均匀分布开始：这将是您必须考虑的所有列表。

然后，您的平均复杂性将是所有列表除以$ n！$的步骤数的总和。

对于给定列表$（x_i）_i $，您的算法的步骤数为$ nd $，其中$ d $是元素$ x_i $和他的应有位置$ i $之间的最大距离（但仅当它必须向左移动），即$ max_i（ max（1，i-x_i））$。

然后您进行数学数：对于每个$ d $，找到具有此特定最大距离的列表的数字$ c_d $，然后$ d $的预期值是：

$$ frac1 {n！} sum_ {d = 0}^n { dc_d} $$

这是最难找到$ C_D $的基本想法。也许有一个更简单的解决方案。

编辑：添加了“预期”

Answer 2

回想一下，如果$ i <j $和$ a [i]> a [j] $，将对一对$（a [i]，a [j]）$（resp。$（i，j）$）倒置。

假设您的算法对每个反转执行一个互换，则算法的运行时间将取决于反转的数量。

计算均匀随机排列中预期的反转数很容易：

令$ p $为排列，让$ r（p）$为$ p $。例如，如果$ p = 2,1,3,4 $，则$ r（p）= 4,3,1,2 $。

对于每对索引$（i，j）$，恰好是$ p $或$ r（p）$之一。

由于对的总数为$ n（n-1）/2 $，并且总数和每对恰好在排列的一半中倒置，假设所有排列都可能同样可能，则预期的反转数为：

$$ frac {n（n-1）} {4} $$

Answer 3

掉期数量<迭代数量（在优化和简单的气泡情况下）

反转数=掉期数。

因此，迭代> $ frac {n（n-1）} {4} $

因此，平均情况复杂性为$ omega（n^2）$。但是，由于平均情况不能超过最坏情况，我们知道它是$ o（n^2）$，

这给了我们：平均时间= $ theta（n^2）$

（时间复杂性=迭代的迭代数量>互换> no。交换）

Answer 4

在本文档中，气泡排序的平均时间复杂性达到O（NLOG（n））！http://algo.inria.fr/flajolet/publications/vifl90.pdf