algorithm - 如何模拟算法的执行时间？

Question

算法运行时间有哪些模型？

我们都希望合并排序比冒泡排序更快，并注意到合并排序进行 O(n log n) 与冒泡排序的 O(n²) 比较。

对于其他算法，您计算其他操作(比较和交换除外)，例如指针取消引用、数组查找、固定大小整数的算术等。

还有哪些其他方法可以对执行时间进行建模？

我自己知道的一个方法是计算从磁盘读取和写入磁盘的 block 数；查看我对 When does Big-O notation fail? 的回答以获得冗长的描述。

另一个是计算缓存未命中的次数。这通过查看内存层次结构的所有级别扩展了 I/O 模型。

第三，对于分布式算法(例如在安全的多方计算中)是计算通过网络传输的数据量(通常以通信轮数或消息数来衡量)。

为了预测算法的性能，还有哪些其他有趣的东西可以计算(而不是计算!)？

此外，这些模型有多好？据我所知，对于磁盘上的数据，缓存不经意的算法与 I/O 高效算法相比具有竞争力，但对于内存中的算法则不然.

特别是:这些模型在哪些特定情况下会错误预测相对性能？根据我自己的实验，当数据小到足以放入内存时，Fibonacci 堆不会加速 Dijstra 的最短路径(相对于二进制堆)。

Answer 1

您必须定义一个计算模型，估算每个操作的成本，然后根据这些成本分析您的算法；当然，成本取决于具体的环境和你要部署算法的底层机器的特性，所以这个问题太笼统了。

在算法类(class)中，我们只是假设每次操作的成本为1，所以我们只是计算循环了多少次；在使用主内存的算法中，我们假设每个操作，除了读/写和 I/O 之外，成本为 0(读/写为 1)，依此类推。

这些模型是否与现实紧密相关？这取决于实际情况:您的环境和机器。

您的缓存未命中计算在核心双核上可能是正确的，但在单元处理器上是错误的，例如，您必须手动传输 SPE 内存的内容。