为什么平均情况下插入排序为Θ（n ^ 2）？ [英] Why is insertion sort Θ(n^2) in the average case?
问题描述
插入排序的运行时为Ω（n）（对输入进行排序时）和O（n 2 ）（对输入进行反向排序时）。平均来说，它运行的时间为Θ（n 2 ）。
Insertion sort has a runtime that is Ω(n) (when the input is sorted) and O(n2) (when the input is reverse sorted). On average, it runs in Θ(n2) time.
为什么？例如，为什么平均情况不更接近O（n log n）？
Why is this? Why isn't the average case closer to O(n log n), for example?
推荐答案
要回答这个问题，让我们首先确定我们如何评估插入排序的运行时间。如果我们可以为运行时找到一个很好的数学表达式，则可以操纵该表达式以确定平均运行时间。
To answer this question, let's first determine how we can evaluate the runtime of insertion sort. If we can find a nice mathematical expression for the runtime, we can then manipulate that expression to determine the average runtime.
我们需要掌握的关键条件是运行时插入排序的位数与输入数组中反转的数量密切相关。数组中的求逆是一对元素A [i]和A [j]的相对顺序错误-也就是说，i < j，但A [j]< A [i]。例如，在此数组中：
The key observation we need to have is that the runtime of insertion sort is closely related to the number of inversions in the input array. An inversion in an array is a pair of elements A[i] and A[j] that are in the wrong relative order - that is, i < j, but A[j] < A[i]. For example, in this array:
0 1 3 2 4 5
有一个倒置：应切换3和2。在此数组中：
There is one inversion: the 3 and 2 should be switched. In this array:
4 1 0 3 2
有6个反演：
- 4和1
- 4和0
- 4和3
- 4和2
- 1和0
- 3和2
- 4 and 1
- 4 and 0
- 4 and 3
- 4 and 2
- 1 and 0
- 3 and 2
反演的一个重要属性是排序后的数组中没有反演，因为每个元素都应小于其后的所有元素，并且大于其前的所有元素。
One important property of inversions is that a sorted array has no inversions in it, since every element should be smaller than everything coming after it and larger than everything coming before it.
之所以重要，是因为数量之间存在直接联系插入排序中完成的工作以及原始数组中的反转次数。要看到这一点，让我们回顾一下用于插入排序的快速伪代码：
The reason this is significant is that there is a direct link between the amount of work done in insertion sort and the number of inversions in the original array. To see this, let's review some quick pseudocode for insertion sort:
- 对于i = 2 .. n ：（假设为1索引）
- 设置j = i-1。
- 同时A [j]> A [j + 1]：
- 交换A [j]和A [j + 1]。
- 设置j = j-1。
通常，在确定诸如以下功能的总工作量时这样，我们可以确定内循环完成的最大工作量，然后将其乘以外循环的迭代次数。这将给出一个上限，但不一定是一个严格的界限。更好地说明已完成的总工作量的方法是认识到有两种不同的工作来源：
Normally, when determining the total amount of work done by a function like this, we could determine the maximum amount of work done by the inner loop, then multiply it by the number of iterations of the outer loop. This will give an upper bound, but not necessarily a tight bound. A better way to account for the total work done is to recognize that there are two different sources of work:
- 外部循环2、3，...，n和
- 执行交换的内部循环。
那个外循环总是起作用Θ（n）。但是，内部循环的工作量与整个算法运行期间进行的交换总数成正比。要查看该循环将执行多少工作，我们需要确定在该算法的所有迭代中进行了多少次总交换。
That outer loop always does Θ(n) work. The inner loop, however, does an amount of work that's proportional to the total number of swaps made across the entire runtime of the algorithm. To see how much work that loop will do, we will need to determine how many total swaps are made across all iterations of the algorithm.
这是反转发生的地方。请注意，运行插入排序时，它总是交换数组中的相邻元素，并且仅在两个元素形成倒置时才交换它们。那么，执行交换后，数组中的总反转数会怎样？好吧，在图形上，我们有这个：
This is where inversions come in. Notice that when insertion sort runs, it always swaps adjacent elements in the array, and it only swaps the two elements if they form an inversion. So what happens to the total number of inversions in the array after we perform a swap? Well, graphically, we have this:
[---- X ----] A[j] A[j+1] [---- Y ----]此处，X是
让我们假设我们交换A [j]和A [j + 1]。反转次数会怎样？好吧，让我们考虑一下两个元素之间的任意转换。有6种可能：
Let's suppose that we swap A[j] and A[j+1]. What happens to the number of inversions? Well, let's consider some arbitrary inversion between two elements. There are 6 possibilities:
- 两个元素都在X中，或者两个元素都在Y中，或者一个元素在X中，一个元素在X中。
- 一个元素在X或Y中，另一个元素在A [j]或A中[j + 1]。然后，由于元素的相对顺序没有改变，即使它们的绝对位置可能不变，反转仍然存在。
- 一个元素是A [j]，另一个元素是A [j] j + 1]。
这意味着在执行交换之后，我们将反转的数量减少了一个，因为只有相邻对的反转才消失。这是非常重要的，因为以下原因：如果我们从I反转开始，则每个交换将使该数目恰好减少1。一旦没有反转，就不再执行交换。因此，交换次数等于反转次数！
This means that after performing a swap, we decrease the number of inversions by exactly one, because only the inversion of the adjacent pair has disappeared. This is hugely important for the following reason: If we start off with I inversions, each swap will decrease the number by exactly one. Once no inversions are left, no more swaps are performed. Therefore, the number of swaps equals the number of inversions!
鉴于此，我们可以将插入排序的运行时间准确地表示为Θ（ n + I），其中I是原始数组的求逆数。这符合我们的原始运行时范围-在排序数组中，存在0个反转，并且运行时为Θ（n + 0）=Θ（n）；在反向排序数组中，存在n（n-1 ）/ 2反演，并且运行时间为Θ（n + n（n-1）/ 2）=Θ（n 2 ）。
Given this, we can accurately express the runtime of insertion sort as Θ(n + I), where I is the number of inversions of the original array. This matches our original runtime bounds - in a sorted array, there are 0 inversions, and the runtime is Θ(n + 0) = Θ(n), and in a reverse-sorted array, there are n(n - 1)/2 inversions, and the runtime is Θ(n + n(n-1)/2) = Θ(n2). Nifty!
现在，我们有了一种分析给定特定数组的插入排序运行时的超精确方法。让我们看看如何分析其平均运行时间。为此，我们需要对输入的分布进行假设。由于插入排序是一种基于比较的排序算法，因此输入数组的实际值实际上并不重要；只有它们的相对顺序才真正重要。在下文中，我将假设所有数组元素都是不同的，尽管如果不是这种情况，则分析不会有太大变化。我会指出到达那里时脚本偏离的地方。
So now we have a super precise way of analyzing the runtime of insertion sort given a particular array. Let's see how we can analyze its average runtime. To do this, we'll need to make an assumption about the distribution of the inputs. Since insertion sort is a comparison-based sorting algorithm, the actual values of the input array don't actually matter; only their relative ordering actually matters. In what follows, I'm going to assume that all the array elements are distinct, though if this isn't the case the analysis doesn't change all that much. I'll point out where things go off-script when we get there.
为解决此问题，我们将引入一堆形式的指标变量X ij ，其中X ij 是一个随机变量，如果A [i]和A [j]形成一个倒数，则为1，否则为0。这些变量将有n（n-1）/ 2个，每对不同的元素对一个。请注意，这些变量说明了数组中每个可能的求逆。
To solve this problem, we're going to introduce a bunch of indicator variables of the form Xij, where Xij is a random variable that is 1 if A[i] and A[j] form an inversion and 0 otherwise. There will be n(n - 1)/2 of these variables, one for each distinct pair of elements. Note that these variables account for each possible inversion in the array.
鉴于这些X，我们可以定义一个新的随机变量I，该变量I等于数组。这将由X的总和给出。
Given these X's, we can define a new random variable I that is equal to the total number of inversions in the array. This will be given by the sum of the X's:
I =Σ X ij
我们对E [I]感兴趣，E [I]是数组中期望的反转次数。使用期望线性，这是
We're interested in E[I], the expected number of inversions in the array. Using linearity of expectation, this is
E [I] = E [Σ X ij ] =Σ E [X ij ]
E[I] = E[Σ Xij] = Σ E[Xij]
所以现在我们可以得到E [X ij ]，我们可以确定预期的反转次数以及预期的运行时间！
So now if we can get the value of E[Xij], we can determine the expected number of inversions and, therefore, the expected runtime!
幸运的是，因为所有X ij 是二进制指标变量，我们有
Fortunately, since all the Xij's are binary indicator variables, we have that
E [X ij ] = Pr [X ij = 1] = Pr [A [i]和A [j]是反型]
E[Xij] = Pr[Xij = 1] = Pr[A[i] and A[j] are an inversion]
那么，给定一个无重复的随机输入数组，A [i]和A [j]是反演的概率是多少？好吧，一半的时间A [i]小于A [j]，另一半的时间A [i]大于A [j]。 （如果允许重复，则会有一个偷偷摸摸的额外术语来处理重复，但我们暂时将其忽略）。因此，A [i]和A [j]之间存在求逆的概率为1 /2。因此：
So what's the probability, given a random input array with no duplicates, that A[i] and A[j] are an inversion? Well, half the time, A[i] will be less than A[j], and the other half of the time A[i] will be greater than A[j]. (If duplicates are allowed, there's a sneaky extra term to handle duplicates, but we'll ignore that for now). Consequently, the probability that there's an inversion between A[i] and A[j] is 1 / 2. Therefore:
E [I ] =Σ E [X ij ] =Σ （1/2）
E[I] = ΣE[Xij] = Σ (1 / 2)
由于总和中包含n（n-1）/ 2个项，所以计算得出
Since there are n(n - 1)/2 terms in the sum, this works out to
E [I] = n（n-1）/ 4 =Θ（n 2 ）
因此，根据期望，会有Θ（n 2 ）反转，因此可以预期运行时将是Θ（n 2 + n）= Θ（n 2 ）。这解释了为什么插入排序的平均情况行为为Θ（n 2 ）。
And so, on expectation, there will be Θ(n2) inversions, so on expectation the runtime will be Θ(n2 + n) = Θ(n2). This explains why the average-case behavior of insertion sort is Θ(n2).
希望这会有所帮助！
这篇关于为什么平均情况下插入排序为Θ（n ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
