计算插入排序的时间复杂度

Question

我试图理解插入排序的时间复杂度。我卡在了 while 循环中。我无法理解循环执行多少次

InsertionSort(A)
for j = 2 to A.length
key = A[j]
i = j - 1
while i>0 and A[i]>key
A[i+1] = A[i]
i = i - 1
A[i+1] = key

我知道 for 循环执行 n+1 次，循环中的每个语句执行 n 次 而循环也执行 n 次 但是，我不明白的是"在最坏和最好的情况下，while 循环下的语句执行了多少次？

Answer 1

在最坏的情况下，A按降序排序，这意味着对于第j个条目，内部循环将运行j次(给出或接受"+1"或"-1"......令人高兴的是，有一个公式：正如高斯在胁迫下自发发现的那样，将所有数字从1到n相加得出n*(n+1)/2的结果。

由于我们只关心复杂性而不是实际值，因此我们可以关闭常数和乘法因子，最终得到O(n^2)。

撇开玩笑不谈，循环中存在循环这一事实强烈表明O(n^2)内部循环计数是线性有界的 - 它在这里。

最好的情况是，A已经按升序排序，内部循环将根本不进入，整体复杂性将O(n)。

一般情况在很大程度上取决于你预期的"无序"是什么样子的。例如，如果你的列表基本上总是已经排序，并且只有很少的、非常本地的切换，那么排序会表现得很大。