c++ - 为什么这些算法运行得比它们应该的要快？

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

复杂性与渐近最坏情况下的行为有关。

...最坏的情况...

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

...渐近...

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

话虽如此，在实践中，仅复杂性并不是最有用的指标，但如果您确实关心性能，则需要进行衡量。