有人可以向我解释为什么插入排序的最坏情况是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项占主导地位)