为什么在平均情况下插入排序Θ(n ^ 2)？

Question

插入排序的运行时间为Ω(n)(当输入已排序时)和O(n ²)(当输入反向排序时).平均而言,它在Θ(n ²)时间内运行.

为什么是这样？例如,为什么平均情况不接近O(n log n)？

Answer 1

要回答这个问题,我们首先确定如何评估插入排序的运行时.如果我们可以为运行时找到一个很好的数学表达式,那么我们可以操作该表达式来确定平均运行时间.

我们需要的关键观察是插入排序的运行时间与输入数组中的反转次数密切相关.数组中的反转是一对元素A [i]和A [j],它们的相对顺序错误 - 即i <j,但是A [j] <A [i].例如,在这个数组中:

0 1 3 2 4 5

有一个倒置:3和2应该切换.在这个数组中:

4 1 0 3 2

有6个反转:

• 4和1
• 4和0
• 4和3
• 4和2
• 1和0
• 3和2

反转的一个重要特性是排序数组中没有反转,因为每个元素应该小于它之后的所有元素,并且大于它之前的所有元素.

这一点很重要的原因是插入排序中完成的工作量与原始数组中的反转次数之间存在直接关联.为了看到这个,让我们回顾一下插入排序的一些快速伪代码:

• 对于i = 2 .. n :(假设1索引)
  • 设置j = i - 1.
  • 而A [j]> A [j + 1]:
    • 交换A [j]和A [j + 1].
    • 设置j = j - 1.

通常,在确定这样的函数完成的工作总量时,我们可以确定内部循环完成的最大工作量,然后将其乘以外部循环的迭代次数.这将给出上限,但不一定是紧束缚.考虑完成的总工作的更好方法是认识到有两种不同的工作来源:

• 外循环,计数2,3,...,n和
• 内循环,执行交换.

该外环总是做Θ(n)工作.然而,内部循环执行的工作量与算法的整个运行时间内的交换总数成比例.要了解该循环将完成多少工作,我们需要确定在算法的所有迭代中进行了多少次交换.

这就是反转的地方.请注意,当插入排序运行时,它总是交换数组中的相邻元素,并且只有在它们形成反转时才交换这两个元素.那么在我们执行交换后,数组中的反转总数会发生什么变化？好吧,从图形上看,我们有:

 [---- X ----] A[j] A[j+1] [---- Y ----]

这里,X是交换对之前的数组的一部分,Y是交换对之后的数组的一部分.

我们假设我们交换A [j]和A [j + 1].倒数的数量会发生什么变化？好吧,让我们考虑两个元素之间的任意反转.有6种可能性:

• 两个元素都在X中,或者两个元素都在Y中,或者一个元素在X中,一个元素在Y中.然后反转仍然存在,因为我们没有移动任何这些元素.
• 一个元素在X或Y中,另一个元素是A [j]或A [j + 1].然后反转仍然存在,因为元素的相对排序没有改变,即使它们的绝对位置可能有.
• 一个元素是A [j],另一个元素是A [j + 1].然后在交换后删除反转.

这意味着在执行交换之后,我们将反转次数减少一个,因为只有相邻对的反转消失了.由于以下原因,这非常重要:如果我们从I倒置开始,每次交换都会将数量减少一个.一旦没有倒置,就不再执行交换.因此,掉期数量等于倒数!

鉴于此,我们可以准确地将插入排序的运行时间表示为Θ(n + I),其中I是原始数组的反转次数.这与我们原始的运行时边界匹配 - 在排序的数组中,有0个反转,运行时是Θ(n + 0)=Θ(n),在反向排序的数组中,有n(n - 1)/ 2次反转,运行时间为Θ(n + n(n-1)/ 2)=Θ(n ²).漂亮!

所以现在我们有一种超精确的方法来分析给定特定数组的插入排序的运行时间.让我们看看我们如何分析它的平均运行时间.为此,我们需要对输入的分布做出假设.由于插入排序是一种基于比较的排序算法,因此输入数组的实际值实际上并不重要; 只有他们的相对排序才真正重要 在下文中,我将假设所有数组元素都是不同的,但如果不是这种情况,则分析不会发生太大变化.当我们到达那里时,我会指出哪些东西会偏离脚本.

为了解决这个问题,我们将引入一组X _ij形式的指标变量,其中X _ij是一个随机变量,如果A [i]和A [j]形成反转,则为1,否则为0.这些变量将有n(n - 1)/ 2个,每个不同的元素对应一个.请注意,这些变量说明了数组中每个可能的反转.

给定这些X,我们可以定义一个新的随机变量I,它等于数组中的反转总数.这将由X的总和给出:

I = _ΣXij

我们对E [I]感兴趣,这是阵列中预期的反转次数.使用期望的线性,这是

E [I] = E [ _ΣXij ] =ΣE[X _ij ]

所以现在如果我们可以得到E [X _ij ] 的值,我们就可以确定预期的反转次数,从而确定预期的运行时间!

幸运的是,由于所有X _ij都是二元指示变量,我们就有了

E [X _ij ] = Pr [X _ij = 1] = Pr [A [i]和A [j]是反演]

那么,给定一个没有重复的随机输入数组,A [i]和A [j]是一个反转的概率是多少？那么,一半时间,A [i]将小于A [j],而另一半时间A [i]将大于A [j].(如果允许重复,那么有一个偷偷摸摸的额外术语来处理重复项,但我们现在将忽略它).因此,A [i]和A [j]之间存在反转的概率是1/2.因此:

E [I] =ΣE[X _ij ] =Σ(1/2)

由于总和中有n(n - 1)/ 2项,因此可以得到

E [I] = n(n - 1)/ 4 =Θ(n ²)

因此,在期望时,将存在Θ(n ²)个反转,因此在期望运行时将是Θ(n ² + n)= Θ(n ²).这解释了为什么插入排序的平均情况行为是Θ(n ²).

希望这可以帮助!