谁能解释为什么插入排序的时间复杂度为 Θ(n²)?
我相当确定我将时间复杂度理解为一个概念,但我并不真正了解如何将其应用于这种排序算法。我应该只看数学证明来找到这个答案吗?
最佳答案
平均而言,每次插入必须遍历当前排序列表的一半,同时每一步进行一次比较。该列表每次增加一个。
因此,从长度为 1 的列表开始并插入第一项以获得长度为 2 的列表,我们平均遍历了 0.5(0 或 1)个位置。对于长度为 n+1 的列表,其余为 1.5(0、1 或 2 位)、2.5、3.5、...、n-.5。
这是,通过简单的代数,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)。
关于sorting - 插入排序的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19827193/