algorithm - 插入排序最坏情况运行时间

Question

为什么在最坏情况下插入排序的运行时间复杂度是 n(n-1)/2 ~ n^2？突出除以2？

Answer 1

1. 运行时间不是n(n-1)/2，每个步骤都需要超过 1 台机器 OP（在我知道的所有机器中）。这就是我们通常在算法分析中使用大 O 表示法和“忽略”常量的原因——我们希望使我们的分析通用且独立于平台。

2. 插入排序被分析为n(n-1)/2 = O(n^2)因为它是 算术级数之和。第一次迭代需要 1 步，第二次需要 2 步，.. 第 n 次需要 n 步，所以我们1 + 2 + ... + n = n(n-1)/2从算术级数的总和中得到。

Answer 2

算法介绍在2.1章详细介绍了插入排序，讨论了插入排序的全过程。

最坏的情况是子阵倒序切换引起的。

Answer 3

我知道这已经永远关闭了，但我想为其他试图复习插入排序最坏情况背后的数学的人添加这个。我找到了一个很棒的视频，它以这种方式解释了 n(n-1) / 2 公式：

评估总和：

您首先将其放入系列符号（称为 s）：

s = 1  + 2 + 3 + ... n-3+n-2+n-1

然后反向显示：

s = n-1+n-2+n-3+ ...  3 + 2 + 1

通过将每一对相加将 s 与 s 相加，您将得到：n+n+n+....n+n+n

或者换句话说2s = n(n-1)，因为你有 n，n-1 次，并且你花了其中两个来获得它。

那么你只需要解决 的2s = n(n-1)不等式s = n(n-1) / 2。