为什么插入排序最好的情况大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).

Answer 2

您的"插入排序"的实现很差.

在你的内循环中,你不应该一直扫描到i-1交换每个元素大于ioList[i].相反,您应该向后扫描,i-1直到找到插入新元素的正确位置(即,直到找到小于或等于新元素的元素),并将其插入那里.如果输入已经排序,那么总是立即找到正确的插入点,因此内部循环不执行i-1时间,它只执行一次.

你的排序平均比插入排序更差,因为你总是i+1对外循环的每次迭代进行操作 - 其中一些操作只是一个比较,有些是比较后跟交换.插入排序只需要平均一半,因为对于随机/平均输入,正确的插入点是初始排序段的一半.也可以避免掉期,这样每个操作都是比较加上副本.