如何对算法的执行时间进行建模？

Question

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

我们都期望归并排序比冒泡排序快，注意到归并排序进行O(n log n)次比较，而冒泡排序需要O(n²)次。

对于其他算法，您需要计算其他操作（而不是比较和交换），例如指针引用、数组查找、固定大小整数的算术运算等。

还有哪些建模执行时间的方式？

我知道的另一种是计算从磁盘读取和写入的块数；请参阅我在When does Big-O notation fail?中的答案，其中有详细的描述。

另一个是计算缓存未命中的次数。这扩展了I/O模型，考虑所有内存层次。

第三个是针对分布式算法（例如安全多方计算）的，它计算通过网络传输的数据量（通常以通信轮次或消息数量来衡量）。

还有哪些有趣的事情可以计数（和不计数！）以预测算法的性能？

这些模型有多好？据我所知，在磁盘上的数据上，缓存无关算法与I/O有效算法相当；但对于内存中的算法，则不然。

特别地：这些模型在哪些具体情况下会错误地预测相对性能？根据我的实验，当数据足够小以适合内存时，斐波那契堆不会加速Dijstra的最短路径（相对于二叉堆）。

- Jonas Kölker

---

“还有哪些有趣的东西可以计数…” 这不是实际的问题吗？也许需要调整标题？ - Aiden Bell

有趣的讨论，但离主题有些偏离。 - ralphtheninja

请注意，格式化O(n2)上的方块正确会得到+1分 :P - Aiden Bell

Answer 1

你需要定义一个计算模型，估计每个操作的成本，然后根据这些成本分析你的算法；当然，成本取决于特定环境和底层机器的特性，因此问题确实太过笼统。

在算法课程中，我们假设每个操作的成本为1，因此只需计算循环次数；在使用主存储器的算法中，我们假设除了I/O读/写以外的每个操作成本为0（I/O读/写成本为1），等等。

这些模型与现实紧密吗？这取决于现实：你的环境和你的机器。

你对缓存未命中的计算可能在双核处理器上是正确的，但在像Cell处理器这样需要手动传输SPE存储器内容的情况下则可能是错误的。

- akappa

---

@akappa，你的回答似乎比我的更优美 :) - Aiden Bell

Answer 2

我认为，无论您使用O(n...)符号来建模执行时间/空间的基础是什么，您都假定了一个标准化的环境。我认为，无论您指定什么样的模型，以及您测量多少个变量来确定它...它只适用于标准化环境。因此，当磁盘I/O在竞争方面较低时，可能不需要考虑这些开销，O(n...)也许就不需要了，如果您明白我的意思。

因此，O(n)模型典型地在输入n的标准化环境中表现出性能。

通过推广，您可以说磁盘读取的顺序是O(n)，或者内存分配的顺序是O(n)，等等。增加压力的外部事件（例如调度）不应该在任何事物的典型时间/空间/发生模型中起作用。

或者我可能没有理解您的观点（我怀疑我可能会错过一些东西）。

- Aiden Bell

Answer 3

对于我所工作的实时平台，最近我发现复制大量数据（例如：在KB范围内，而不是MB范围内）实际上比我预期的要快得多。可能这与今天使用的大缓存有关，或者仅仅是处理器速度非常快。但是效果是，为了避免数据复制，一个人真的不应该过分地扭曲自己的代码。

相反，我真正需要注意的是设备访问和上下文切换。这些越少，越好。

“零缓冲区”设备驱动程序等速度快的日子已经过去了。

- T.E.D.