algorithm - 有人可以向我解释为什么插入排序的最坏情况是 O(n^2) 吗？

Question

有人可以逐步解释我们如何在找到插入排序的最坏情况分析时得到 O(N^2) 吗？我目前正在从 Cormen Intro to Algorithms 一书中阅读对此的解释，但解释有点令人困惑。

Answer 1

简而言之，最坏的情况是您的列表的顺序与您需要的顺序完全相反。在那种情况下:

• 当然，对于第一项，您进行了 0 次比较。
• 对于第二个项目，你将它与第一个项目进行比较，发现它们的位置不对；您进行了 1 次比较。
• 对于第三个，你将它与两者进行比较，发现第三个必须排在最前面。您进行了 2 次比较。
• 继续；对于以下每个值，您再进行一次比较。
• 最后，对于第 n 项，您进行了 n - 1 次比较。

如果将最坏情况的比较次数加起来，您会发现它是0 + 1 + 2 + ... + n-1，这等于 (n^2 - n)/2 最坏情况下的比较，即 O(n^2)。 (决定复杂度的部分是当我们考虑较大的 n 时，在这种情况下，n^2 项占主导地位)