python - 如何通过示例计算给定算法的 O(n, x)？

Question

我想计算给定算法的运行时间 O(n, x) = Theta(n, x) 取决于 n 和 x 大量（> 100）个示例（算法需要多长时间 n 和 x ）。实际上有办法做到这一点吗？

我知道运行时间会随着 n 和 x (!) 的增加而增加，但我认为连贯性太复杂了，无法通过“手动”计算出 O(n, x)，因为 n 或 x mac 会像 n ^ x 一样增加，或者更糟。

顺便提一句。我最喜欢解决这个问题的语言是 Python 或 PHP。

Answer 1

有一个名为Eureqa的免费工具可能会让您感兴趣。你可以给它数据，它会找到适合你数据的候选方程。例如，您在不同的输入大小上运行算法并记录每个的执行时间，然后将这些数据提供给 Eureqa。然后它将为您提供适合您数据的数学方程式。

许多算法的运行时间高度依赖于输入数据中的特定值。因此，这并不总是用于进行渐近分析的好方法，因为您只是不知道您的数据是否正在将算法推向极限。

但是，我们使用渐近分析作为达到目的的一种手段——我们经常希望选择一种可能在现实世界中对现实世界数据运行良好的算法。而且，这就像基准测试，但你会获得很棒的额外数学洞察力。另外，请记住，渐近分析本身有点让步，我们需要简化和降低我们的期望以获得一些简单到有用的答案。

观看他们的 youtube 视频http://www.youtube.com/watch?v=NhC1Qb-PQ5Q

Answer 2

最好的方法是非常仔细地查看算法并分析每个步骤以计算平均和最坏情况运行时类。

如果这不可行，您可以使用相对较小的数字运行算法，并将它们相互比较。如果运行时间按任何参数的顺序是指数的，那么即使相差 10 或 20，它也应该是显而易见的。简单地绘制运行时间，比如说

• x = 10 和 y 在范围内 (50)
• y = 10 和 x 在范围内 (50)
• x 在范围内 (50)，y=x

应该给你一个粗略的想法。当运行时间变大时，您可以提前中止，例如大于(1,1).

这应该会给您一个粗略的估计，但您应该清楚它既不精确（您的测试数据可能无意中遵循某些模式并遇到一个好的案例）也不足够（所涉及的因素可能非常小 - 您不会正确识别，比如说，x + 0.0001 * 1.05^y）。幸运的是，在许多情况下，指数算法的基数明显大于 1。

在 Python 中，您可以使用该timeit模块来正确测量运行时。