c++ - 为什么插入排序最好的情况是大 O 复杂度 O(n)？

Question

以下是我的插入排序代码:

void InsertionSort(vector<int> & ioList)
{
  int n = ioList.size();
  for (int i = 1 ; i < n ; ++i)
  {
    for (int j = 0 ; j <= i ; ++j)
    {
      //Shift elements if needed(insert at correct loc)
      if (ioList[j] > ioList[i]) 
      {
        int temp = ioList[j];
        ioList[j] = ioList[i];
        ioList[i] = temp;
      }
    }
  }
}

算法的平均复杂度为 O(n^2)。

根据我对大 O 表示法的理解，这是因为我们在这种情况下运行了两个循环(外部循环 n-1 次和内部循环 1,2,...n-1 = n(n-1)/2次，因此算法的无症状复杂度为 O(n^2)。

现在我读到最好的情况是输入数组已经排序的情况。在这种情况下，算法的大 O 复杂度为 O(n)。但是我不明白这是怎么可能的，因为在两种情况下(平均情况和最佳情况)我们必须运行相同次数的循环并且必须比较元素。唯一避免的是元素的移动。

那么复杂度计算是否也涉及这个交换操作的一个组成部分？

Answer 1

是的，这是因为您的实现不正确。内部循环应该从 i-1 向下计数到 0，并且一旦找到元素 ioList[j] 就应该终止这已经小于 ioList[i]。

正是由于该终止标准，该算法在最佳情况下在 O(n) 时间内执行:

如果输入列表已经排序，内部循环将立即终止任何 i，即执行的计算步骤数最终与外部循环执行的次数成正比，即 O(n)。