DSA 插入排序时间复杂度

参见 此页面 了解时间复杂度的一般解释。

插入排序时间复杂度

插入排序 的最坏情况是数组已经排序，但最高值排在最前面。因为在这种情况下，每个新值都必须“穿过”数组的整个已排序部分。

以下是插入排序算法对前几个元素执行的操作

• 第一个值已经位于正确位置。
• 第二个值必须与第一个值比较并移动到第一个值后面。
• 第三个值必须与两个值比较并移动到它们后面。
• 第四个值必须与三个值比较并移动到它们后面。
• 等等...

如果我们继续这种模式，我们将得到 \(n\) 个值的总操作数

\[1+2+3+...+(n-1)\]

这在数学中是一个众所周知的级数，可以写成这样

\[ \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \]

对于非常大的 \(n\)，\(\frac{n^2}{2}\) 项占主导地位，因此我们可以通过删除第二项 \(\frac{n}{2}\) 来简化。

使用大 O 符号，我们得到插入排序算法的这种时间复杂度

\[ O(\frac{n^2}{2}) = O(\frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

时间复杂度可以显示为这样

正如你所看到的，当值的数量为 \(n\) 增加时，插入排序使用的时间快速增加。

插入排序模拟

使用下面的模拟来查看理论时间复杂度 \(O(n^2)\)（红线）与实际插入排序的操作数的比较。

对于插入排序，最佳情况、平均情况和最坏情况之间存在很大差异。你可以通过运行上面的不同模拟来查看这一点。

上面的红线代表理论上限时间复杂度 \(O(n^2)\)，在这种情况下，实际函数是 \(1.07 \cdot n^2\)。

请记住，如果存在一个正常数 \(C\)，使得 \(C \cdot g(n)>f(n)\)，那么函数 \(f(n)\) 被称为 \(O(g(n))\)。

在这种情况下，\(f(n)\) 是插入排序使用的操作数，\(g(n)=n^2\)，而 \(C=1.07\)。