performance - 理论 VS 实际运行时间评估

Question

假设有一个我们知道其渐近行为的算法，例如O(n^4)。我们想评估该算法在现实世界中的性能。

现在，一种天真的方法是多次运行我们的算法，并根据输入的大小绘制运行时间。我们将在 x-y 平面上得到一组点。我们如何验证我们的实现确实是 O(n^4)？曲线拟合是个好主意吗？还有其他更有效的方法吗？

非常感谢。

Answer 1

O(N^4) 的意思是无论 N 变得多大，运行时间总是小于或等于 C+K*N^4 形式的曲线，其中 C 和 K 是任意的常数。因此，除了某种数学证明(可能通过递推关系)之外，唯一的方法就是实验。

因此，您将一系列数据集扔给它，其中 N 在一定范围内变化，并绘制运行时间。然后你拟合 C+K*N^4 形式的曲线，你试图在其中找到 C 和 K 的最小值，试图说服自己实验数据永远不会超过曲线。

当然，这并不能证明什么，因为您无法尝试 N 的所有值。即使您认为自己的曲线很好，也不能假设没有更高的 N 值会破坏您的曲线。您只能说，对于小于或等于您尝试过的值的 N 值，曲线是好的，并且它保持良好的可能性是合理的。