sorting - 插入排序的时间复杂度

Question

谁能解释为什么插入排序的时间复杂度为 Θ(n²)？

我相当确定我将时间复杂度理解为一个概念，但我并不真正了解如何将其应用于此排序算法。我应该只看数学证明来找到这个答案吗？

Answer 1

平均而言，每次插入必须遍历当前排序列表的一半，同时每一步进行一次比较。该列表每次增加一个。

因此，从长度为 1 的列表开始并插入第一项以获得长度为 2 的列表，我们平均遍历 0.5（0 或 1）个位置。对于长度为 n+1 的列表，其余为 1.5（0、1 或 2 位）、2.5、3.5、...、n-.5。

这是，通过简单的代数，1 + 2 + 3 + ... + n - n*.5 = (n(n+1) - n)/2 = n^2 / 2 = O(n^2)

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

在最好的情况下，您可以通过一次比较找到顶部元素的插入点，因此您有 1+1+1+ (n 次) = O(n)。

Answer 2

插入排序算法的最坏情况时间复杂度为 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)

Answer 3

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