如何推导给定插入排序算法的最坏时间复杂度？

先把你给出的算法代码格式化展示：

for (i = 0; i<= n-2; i++)
 do {
  j: = n-1 
  while (j > i)
   do {
    if A[j] < A[j-1] then 
      temp: = A[j] 
      A[j]: = A[j-1] 
      A[j-1]:= temp 
      } 
   j: = j-1 
  }
 }

步骤1：明确最坏情况场景 #

该算法是插入排序的一种变体（从数组末尾向前冒泡，把当前未排序区间的元素逐步交换到正确位置），它的最坏情况出现在输入数组完全逆序时——此时每一次if A[j] < A[j-1]的判断都会成立，必须执行交换操作。

步骤2：统计循环执行次数 #

• 外层for循环：i的取值范围是0 ≤ i ≤ n-2，总共执行n-1次（从0到n-2共(n-2)-0+1 = n-1个值）。
• 内层while循环：对于每一个i，j从n-1开始递减，直到j > i不成立，也就是j会取n-1, n-2, ..., i+1，总共执行(n-1) - (i+1) + 1 = n - i -1次。

步骤3：计算总操作次数 #

我们只需要统计主导操作（这里是比较+交换的组合）的总次数，求和公式为：
$$\sum_{i=0}^{n-2} (n - i - 1)$$

将变量替换为k = n - i -1，当i=0时k=n-1，i=n-2时k=1，求和式可转化为：
$$\sum_{k=1}^{n-1} k = \frac{(n-1) \times n}{2} = \frac{n^2 - n}{2}$$

步骤4：推导时间复杂度 #

时间复杂度关注的是当n趋近于无穷大时的量级，$\frac{n^2 -n}{2}$中最高次项是$\frac{1}{2}n^2$，低次项和系数对量级没有影响，因此该算法的最坏时间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者David Smart