插入排序的时间复杂度

Question

任何人都可以解释为什么插入排序的时间复杂度为Θ(n²)？

我很确定我将时间复杂性理解为一个概念,但我并不真正理解如何将它应用于这种排序算法.我应该只看数学证据来找到这个答案吗？

Answer 1

平均每个插入必须遍历当前排序列表的一半,同时每步进行一次比较.该列表每次增长一个.

因此,从长度为1的列表开始并插入第一个项目以获得长度为2的列表,我们平均遍历.5(0或1)个位置.其余为1.5(0,1或2位),2.5,3.5,...,n-.5,长度为n + 1的列表.

这是通过简单代数,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).