为什么插入排序的最佳情况是大O复杂度O(n)? [英] why is Insertion sort best case big O complexity O(n)?

问题描述

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

Following is my insertion sort code:

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).

The average complexity of the algorithm is O(n^2).

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

From my understanding of big O notation, this is because we run two loops in this case(outer one n-1 times and inner one 1,2,...n-1 = n(n-1)/2 times and thus the resulting asymptomatic complexity of the algorithm is O(n^2).

现在我已经读到最好的情况是输入数组已经排序的情况. 在这种情况下，算法的最大O复杂度为O(n).但是我无法理解这是如何实现的，因为在两种情况下(平均和最佳情况下)，我们都必须将循环运行相同的次数，并且必须对元素进行比较.唯一可以避免的是元素的移动.

Now I have read that best case is the case when the input array is already sorted. And the big O complexity of the algorithm is O(n) in such a case. But I fail to understand how this is possible as in both cases (average and best case) we have to run the loops the same number of times and have to compare the elements. The only thing that is avoided is the shifting of elements.

那么复杂度计算是否也包含此交换操作的一部分?

So does complexity calculation also involve a component of this swapping operation?

推荐答案

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

Yes, this is because your implementation is incorrect. The inner loop should count backward from i-1 down to 0, and it should terminate as soon as it finds an element ioList[j] that is already smaller than ioList[i].

由于这种终止准则，该算法在最佳情况下的执行时间为O(n):

It is because of that termination criterion that the algorithm performs in O(n) time in the best case:

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

If the input list is already sorted, the inner loop will terminate immediately for any i, i.e. the number of computational steps performed ends up being proportional to the number of times the outer loop is performed, i.e. O(n).

这篇关于为什么插入排序的最佳情况是大O复杂度O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！