存在哪些算法运行时间模型？
我们都期望归并排序比冒泡排序更快，并注意归并排序使得 O(n log n) 与 O(n 2 ) 的冒泡排序进行比较。
对于其他算法，您可以计算其他操作（比较和交换除外），例如指针取消引用、数组查找、固定大小整数的算术等。
还有哪些其他方法来模拟执行时间？
我自己知道的一个是计算从磁盘读取和写入磁盘的块数；请参阅我对 Big-O 表示法何时失败的回答？冗长的描述。
另一个是计算缓存未命中的数量。这通过查看内存层次结构的所有级别来扩展 I/O 模型。
第三，对于分布式算法（例如在安全多方计算中），是计算通过网络传输的数据量（通常以通信轮数或消息数来衡量）。
为了预测算法的性能，还有哪些其他有趣的事情可以计算（而不是计算！）？
另外，这些模型有多好？ 据我所知，缓存遗忘算法与磁盘数据的 I/O 效率算法相比具有竞争力，但对于内存算法则不然。
特别是：这些模型在哪些特定情况下错误地预测了相对性能？根据我自己的实验，当数据小到足以放入内存时，斐波那契堆不会加速 Dijstra 的最短路径（相对于二进制堆）。
您必须定义一个计算模型，估算每个操作的成本，然后根据这些成本分析您的算法；当然，成本取决于特定环境和您要部署算法的底层机器的特性，所以这个问题实在是太笼统了。
在算法课程中，我们只是假设每个操作花费 1，所以我们只计算循环的次数；在与主存一起工作的算法中，我们假设每个操作，除了 I/O 的读/写，成本为 0（和读/写 1），依此类推。
这些模型与现实紧密吗？这取决于现实：您的环境和您的机器。
您的缓存未命中计算在双核上可能是正确的，但在单元处理器上是错误的，例如，您必须手动传输 SPE 内存的内容。
我认为无论您使用 O(n...) 符号对执行时间/空间进行建模的基础如何，您都在假设一个规范化的环境。我认为无论您指定什么模型，无论您测量多少变量来确定它......它只适用于标准化环境。因此，当磁盘 I/O 在竞争方面较低时，可能不需要 O(n...) 来考虑这些开销......如果你明白我的意思的话。
因此 O(n) 对输入 n 在标准化环境中的典型性能进行建模。
通过扩展，您可以说磁盘读取的顺序为 O(n)，或者内存分配的顺序为 O(n)，依此类推。增加压力的外部事件（例如调度）不应该在典型的时间/空间/任何事情发生的模型中发挥作用。
或者也许我错过了你的观点（我怀疑我可能是）。
对于我工作的实时平台，最近我发现复制大量数据（例如：在 KB 范围内，而不是 MB 范围内）实际上比我受过训练的预期要快得多。这可能与当今使用的大型缓存有关，或者可能只是处理器速度极快。但效果是，人们真的不应该再为了避免数据复制而过度扭曲自己的代码。
相反，我真正需要注意的是设备访问和上下文切换。这些越少越好。
“零缓冲”设备驱动程序与速度同义的时代已经结束。