插入比较#似乎太大
问题描述:
我很困惑,如果这些比较数字应该是100个随机两位数字的向量值这么大。完整程序 - >安全链接:https://ideone.com/oybDbD程序输出位于链接的底部页面。欣赏输入。插入比较#似乎太大
int insertionSort (vector<int> &v) {
int j, temp, counter = 0;
for (int i = 1; i < v.size(); i++) {
j = i;
while (++counter && j > 0 && v[j] < v[j-1]){
temp = v[j];
v[j] = v[j-1];
v[j-1] = temp;
j--;
}
}
return counter;
}
答
插入排序是O(N^2)
的平均情况下的性能(见wiki entry)。对于100个元素的向量,因此预期的比较次数为O(10000)
。以2656出场,或者在你的第二轮比赛中,4995,因此比你预期的要低,低于。
只是为了澄清,插入排序的预期比较数是10,000?感谢您的帮助:) – Lightypulse
@Lightypulse:不完全。在这种情况下,比较的平均次数是“O(N^2)”,其计算结果为“O(10000)”。期望值进入统计数据,这是一个不同的球赛。我很抱歉在那里缺乏透明度。此外,[这个答案](https://*.com/questions/17055341/why-is-insertion-sort-%CE%98n2-in-the-average-case)可以帮助你更好地理解发生了什么。 – Richard
@Lightypulse:如果我的回答对你有帮助,可以通过点击箭头或选中标记来点击或接受它。 – Richard