为什么这些算法的运行速度比正常情况下要快？

Question

我创建了一个C++程序，该程序输出算法的输入大小与执行时间(微秒)，并将结果写入.csv文件。在LibreOffice Calc中导入.csv并绘制图形时，

我注意到，即使我搜索的元素不在数组中，对输入大小最大为10000的二进制搜索的运行时间也是恒定的。类似地，对于相同的输入大小，合并排序似乎在线性时间内运行，而不是在所有情况下运行的线性对数时间。

插入排序和冒泡排序运行得很好，输出图非常接近它们最坏的情况下的二次复杂性。

我从一个文件中提供了输入数组。对于n= 5，文件的内容如下所示。每行代表一个输入数组：

5 4 3 2 1 
4 3 2 1 
3 2 1 
2 1 
1

运行插入排序的results.csv文件为：

Input,Time(ms)
5,4
4,3
3,2
2,2
1,2

最大输入100的二进制搜索图是here。

同样，最大输入1000的合并排序图是here，它看起来很像是线性的(表中的值也表明是线性的)。

任何关于为什么会发生这种情况的帮助都将不胜感激。

以下是github存储库的源代码链接：https://github.com/dhanraj-s/Time-Complexity

Answer 1

复杂性是关于渐近的最坏情况行为。

...worst案例..。

如果输入允许，即使是二次算法也可能退回到线性变量。它的复杂度仍然是二次的，因为对于最坏的情况，算法只能保证二次运行时。

...asymptotic...

很可能算法的渐近行为只在输入大小比您选择的大得多的情况下才开始稳定下来。

也就是说，在实践中，复杂性本身并不是最有用的度量标准，但如果您确实关心性能，则需要进行度量。