为什么插入排序在平均情况下的时间复杂度为Θ(n^2)？

Question

为什么插入排序在平均情况下的时间复杂度为Θ(n^2)？

algorithmsortingbig-oinsertion-sort

28

插入排序的运行时间在输入数据已经排序的情况下为Ω(n)，在输入数据为逆序的情况下为O(n²)，平均情况下它的运行时间为Θ(n²)。

为什么会这样呢？例如，为什么平均情况不更接近于O(n log n)呢？

- templatetypedef

4个回答

2

为了好玩，我写了一个程序，它可以遍历大小为n的向量的所有数据组合，计算比较次数，并发现最好的情况是n-1（完全排序），最坏的情况是(n*(n-1))/2。

以下是不同n的一些结果：

  n min     ave     max ave/(min+max) ave/max

  2   1     1         1        0.5000
  3   2     2.667     3        0.5334
  4   3     4.917     6        0.5463
  5   4     7.717    10        0.5512
  6   5    11.050    15        0.5525
  7   6    14.907    21        0.5521
  8   7    19.282    28        0.5509
  9   8    24.171    36        0.5493
 10   9    29.571    45        0.5476
 11  10    35.480    55        0.5458
 12  11    41.897    66        0.5441

看起来平均值更接近最小值而不是最大值。

编辑：一些额外的数值

 13  12    48.820    78        0.5424        
 14  13    56.248    91        0.5408

编辑：15的值

 15  14    64.182   105        0.5393

编辑：选择更高的值

 16  15    72.619   120        -       0.6052
 32  31   275.942   496        -       0.5563
 64  63  1034.772  1953        -       0.5294
128 127  4186.567  8128        -       0.5151
256 255 16569.876 32640        -       0.5077

最近我编写了一个程序，用于计算插入排序在较高n值情况下的平均比较次数。通过这些数据，我得出结论：当n趋近于无穷大时，平均情况会趋近于最坏情况除以二。

- Olof Forshell

看一下平均运行时间的增长率。注意到当输入大小加倍时，它大约增加了四倍。这意味着它是二次的，因此更接近于最大值而不是最小值。我敢打赌，如果你得到更大的n值，最小值和平均值之间的差距会更大得多。 - templatetypedef

@templatetypedef 我的错误。当n加倍时，最小值和最大值稳定在2x和4x的恒定增长。通过查看平均数据，我得出结论它将稳定在约3.7x的附近。 - Olof Forshell

这相当于n的1.888次方。 - Olof Forshell

你计算过更大的n吗？我拥有的证明预测二次增长，在较小的n中，低阶项仍然会贡献很多。 - templatetypedef

我正在计划何时运行n=15，需要15！（1.31 * 10 ^ 12）个不同的组合，每个组合平均要进行64-65次比较。我的CPU运行速度为2.67 GHz或2.67 * 10 ^ 9，这意味着31646 * 每个比较的平均时钟周期数。至少需要超过24小时的执行时间。 - Olof Forshell

我说你完全正确。插入排序无法获得n^2次操作。O(n*(n-1)/2)是最坏情况。 - Ralph

0

大多数算法的平均情况与最坏情况相同。为了理解这一点，让我们称 O 为最坏情况，Ω 为最好情况。假设当 n 趋近于无穷大时，O >= Ω。对于大多数分布，平均情况将接近于最好和最坏情况的平均值 - 即 (O + Ω)/2 = O/2 + Ω/2。由于我们不关心系数，并且 O >= Ω，因此这与 O 相同。

显然，这是一种过度简化的说法。有些运行时间分布是倾斜的，使得平均情况等于最坏情况和最好情况的平均值的假设是无效的。但这应该可以给你一个不错的直觉。

正如评论中 templatetypedef 所提到的，一些例子包括快速排序/快速选择、BST 查找（除非平衡树）、哈希表查找和单纯形法。

- Aaron Dufour

许多重要的算法在最坏情况下的运行时间与平均情况下的运行时间不同：例如快速排序、快速选择、二叉搜索树查找、哈希表查找和单纯形法。 - templatetypedef

@templatetypedef 我很确定有一些，但是我什么都想不出来。谢谢你的建议！ - Aaron Dufour

0

让我们来看一下程序：通用表示。

         
Loop : j = 1 to n 
{
   temp = array[j]
   k = j - 1
   
   Loop until : ( k > 0 ) and ( array[k] > temp ) {
       array[k+1] = array[k]     // shifting one element at a time
       k = k - 1
   }

   array[k+1] = temp

}

外层循环：1 - 2 - 3 - 4 - 5 - .... n

内层循环：对于每个元素都有自己的内层循环

让我们以数组为例：[ 3, 2, 9, 1, 2, 6, 5 ]（平均情况）

                 3  -  2  -  9  -  1  - ..... n
                       |     |     |          |
    no. of loop        1     0     3       (n + 1) / 2  

 (n+1)/2 -> (multiple cases. so, using median of all probabilities)

因此，对于每个元素 (n)，循环运行 ( (n+1)/2 ) 次。

 -> n(n+1)/2 
 -> (n2 + n )/2
 -> n2 + n            // drop constants
 -> n2                // drop lower order terms

因此，即使对于平均情况，时间复杂度也为：O(n*n)

注意：所有与输入规模成比例增长的循环都具有线性时间复杂度O(n)。如果您只循环遍历数组的一半，那么这仍然是O(n)。请记住我们会删除常数，所以1/2 n => O(n)。

- Saurabh Mehra

为了使这个论点足够严谨，您需要解释为什么每个项目平均会向下移动（n+1）/2个位置。实际数量比这个要低，因为早期的项目很可能被交换的次数要少得多。 - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

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

我们需要关注的关键观察是，插入排序的运行时间与输入数组中的逆序对数量密切相关。在数组中，逆序对是一对元素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 = Σ X_ij

我们对E[I]感兴趣，它是数组中反转的期望数量。使用期望的线性性，这可以表示为：

E[I] = E[Σ X_ij] = Σ 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²)。

希望这可以帮到你！