performance - 将程序的实际运行时间缩放到理论运行时间

Question

我已经获得了不同输入大小的程序运行时间（CPU 时间）（以秒为单位），我想构建一个图表来显示 CPU 时间和理论运行时间（例如O(n³)）。

我应该如何扩展 CPU 时间？

Answer 1

CPU 时间和 BigO 表示法是两个不同的东西，因此不应将它们进行比较。

BigO 表示法背后的想法是，它为您提供了一种独立于平台的方法来衡量算法的效率。根据 CPU 的速度、负载等，不同的算法将在不同的时间在不同的 CPU 上运行。因此，CPU 不是一个好的指标。任何算法的问题是它是否尽可能高效地编写。

这就是 BigO 表示法的用武之地。它衡量完成任务所需的操作数量，因此与平台无关。如果您减少完成一项任务所需的操作数量，那么——在其他条件相同的情况下——无论平台如何，您都将提高效率。

因此，计算程序中的操作数并从中推导出 BigO 复杂度。然后你可以根据理论来衡量它。