以下是我的插入排序代码:
算法的平均复杂度为O(n^2)。从我对大O符号的理解来看,这是因为在这种情况下我们运行了两个循环(外部循环n-1次,内部循环1,2,...n-1 = n(n-1)/2 次),因此算法的渐进复杂度为O(n^2)。
现在我已经了解到最佳情况是输入数组已经排序过的情况。在这种情况下,算法的大O复杂度是O(n)。但我无法理解这是如何可能的,因为在两种情况下(平均和最佳情况)我们都必须运行相同数量的循环并比较元素。唯一避免的是元素的移动。
因此,复杂性计算是否也涉及这个交换操作的组成部分?
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)。但我无法理解这是如何可能的,因为在两种情况下(平均和最佳情况)我们都必须运行相同数量的循环并比较元素。唯一避免的是元素的移动。
因此,复杂性计算是否也涉及这个交换操作的组成部分?