谁能解释一下为什么插入排序的时间复杂度是 θ(n²)？
我相当确定我将时间复杂度理解为一个概念，但我并不真正理解如何将其应用于此排序算法。我应该只通过数学证明来找到这个答案吗？
平均而言，每次插入必须遍历当前排序列表的一半，同时每一步进行一次比较。该列表每次都会增加一。
因此，从长度为 1 的列表开始，插入第一项以获得长度为 2 的列表，我们平均遍历 0.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)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
