插入排序的时间复杂度

Question

有人能解释一下为什么插入排序的时间复杂度是Θ(n²)吗？

我相当确定我理解时间复杂度的概念，但我不太明白如何将其应用到这个排序算法上。我应该寻找数学证明来找到答案吗？

- Drake Drinnon

---

自己编写数学证明只会加强您的理解。通常最棘手的部分实际上是设置。例如，首先您应该澄清您是否想要算法的最坏情况复杂度或其他内容（例如平均情况复杂度）。其次，您需要定义在分析中什么算作实际操作。对于基于比较的排序算法（如插入排序），通常我们将比较定义为需要 O(1) 时间，交换需要 O(1) 时间。您可以自行判断这是否是有效的指标。从那时起，只需应用定义即可。 - rliu

Answer 1

平均每个插入操作必须遍历当前排序好的列表的一半，并在每一步中进行一次比较。列表每次增加一个元素。

因此，从长度为1的列表开始，并插入第一个项目以获得长度为2的列表时，我们平均需要遍历0.5（0或1）个位置。其他情况下的平均遍历次数为1.5（0、1或2个位置）、2.5、3.5，...，n-.5（列表长度为n+1时）。

通过简单的代数运算，可以得到：1 + 2 + 3 + ... + n - n * 0.5 = (n(n+1) - n)/2 = n^2/2 = O(n^2)

请注意，这是平均情况。在最坏情况下，列表必须完全遍历（您总是将下一个最小的项插入到升序列表中）。然后，您需要1 + 2 + ... + n，这仍然是O(n^2)。

在最好的情况下，您通过一次比较找到插入点，因此您需要1+1+1+（n次）= O(n)。

- Gene

---

好的回答。我只想补充两件事：

1. Peter Crummins在这里有一套不错的笔记http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/
2. 在最坏的情况下，我们有最阴险的输入。也就是说，列表完全是反向排序的。因此，每次迭代都需要进行“j”次遍历。计算时间T(n)的公式为sum(\theta(j))，其中j = 2:n。（假设列表从1开始索引）

- hAcKnRoCk

@MhAcKN 没错。这就是为什么针对大数据的排序实现要特别注意“坏”情况。通常情况下（这只是一个非常粗略的经验法则），如果数据可能增长到100个或更多，你不想使用插入排序。 - Gene

谢谢Gene。我一直在理论上计算时间复杂度，但是我一直在琢磨渐近符号中的Theta实际上量化了什么。所以我想它应该量化所需的遍历次数。只有一个小问题，如果在其中一种插入排序中实现>或=运算符更有效率，那么我们如何改变Theta()符号来反映这一点。还是我想太多了？ - hAcKnRoCk

@MhAcKN 你关注细节是正确的。 \ O， \ Omega，\ Theta等涉及函数之间的关系，而不是运行时间。 当我们将它们用于描述运行时间时，忽略输入的性质和其他粗糙因素会导致问题。 在大多数排序算法的表征中，使用\ O，\ Theta等来描述的函数是“与导致最坏性能的数据的输入数据数量相比较的比较次数”。 因此，比较的运行时间已经被纳入分析中了。 根据这个定义，插入排序的时间复杂度是（如你所述）\ Theta（n ^ 2）。 - Gene

最佳情况实际上比N少1：在最简单的情况下，当N=2时需要进行一次比较，当N=3时需要进行两次比较，以此类推。在最坏的情况下，比较的次数为N*(N-1)/2：在最简单的情况下，当N=2时需要进行一次比较，当N=3时需要进行三次比较（1+2），当N=4时需要进行六次比较（1+2+3），以此类推。 - Olof Forshell

@OlofForshell 嗯，-1 取决于具体实现的细节。如果使用索引比较来停止插入点搜索，则需要进行 N-1 次键比较和 N 次索引比较。如果使用哨兵，则仅需要进行 N 次键比较。 - Gene

Answer 2

它只适用于数组/列表 - 即具有O(n)插入/删除时间的结构。对于其他数据结构可能会有所不同。例如，对于跳表，它将是O(n * log(n))，因为在跳表中可以进行O(log(n))的二进制搜索，但插入/删除将是常量。

- vladich

Answer 3

插入排序算法的最坏时间复杂度为O(n^2)。当数组中的元素按降序排列且你想将其按升序排序时，插入排序的最坏情况出现。

假设你有一个数组

Step 1 => | 4 | 3 | 2 | 1 | No. of comparisons = 1  |  No. of movements = 1 
Step 2 => | 3 | 4 | 2 | 1 | No. of comparisons = 2  |  No. of movements = 2
Step 3 => | 2 | 3 | 4 | 1 | No. of comparisons = 3  |  No. of movements = 3
Step 4 => | 1 | 2 | 3 | 4 | No. of comparisons = 4  |  No. of movements = 4

T(n) = 2 + 4 + 6 + 8 + ---------- + 2(n-1)

T(n) = 2 * ( 1 + 2 + 3 + 4 + -------- + (n-1))

T(n) = 2 * (n(n-1))/2

T(n) = O(n^2)

- Akshay