我有一个C程序，对于以下数量的输入，该程序在以下时间内执行:
23 0.001s
100 0.001s
我尝试找到一个公式，但没有成功。据我所知，时间有时会加倍，有时不会，这就是为什么我找不到这个公式。
有什么想法吗？
注释
1) 我用 CPU 时间(用户+系统)来衡量这一点。
2)我的程序使用快速排序
2) 我的程序的渐近运行时分析/复杂性是 O(NlogN)
最佳答案
绘制此图看起来非常像您遇到了“缓存悬崖” - 您的数据足够大，因此它不能全部适合 CPU 缓存级别，因此必须在更便宜和更昂贵的级别之间交换数据
较低级别的差异可能是由于精度造成的 - 如果您增加计时器 block 内的循环 - 这可能会平滑
通常，当遇到缓存悬崖时，eprformace 类似于绘制 O*Q
其中 O 是平均运行时间 - 在您的情况下为 Nlog(N)
Q 是一个阶跃函数，当您传递每个缓存的分配大小时，该函数会增加。 所以 Q=1 低于 L1 大小，10 高于 L1 大小，100 高于 L2 大小，等等(仅作为数字示例)
事实上，有人通过绘制 O(1) 函数并查找性能悬崖时使用的内存来验证其缓存大小:
___
_____-----
L1 | L2 | L3
关于c - 程序运行时的近似公式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19987577/