algorithm - 如何将算法的复杂性转化为计算所需的时间

Question

如果我知道算法的复杂性，我能预测它在现实生活中需要多长时间才能计算出来吗？

更多上下文:我一直在尝试解决大学作业，该作业必须从给定位置找到游戏中的最佳结果。我写了一个算法，它可以工作，但是很慢。复杂度为 O(n)=5^n 。对于 24 个元素，它计算几分钟。我不确定是不是因为我的实现有误，还是这个算法太慢了。有什么方法可以让我估算任何算法应该花费多少时间？

Answer 1

您可以根据外推法得出最坏情况。因此，在 N=1、2、3、4 个元素上花费时间(越多越好)和算法复杂度的 O 符号估计，您可以估计任何有限数量的时间。另一个问题是，随着 N 的增加，这种估计精度会越来越低。

你能用它做什么？搜索此类方法的误差估计算法。在实践中，它通常会提供足够好的结果。

另外请不要忘记模型充分性检查。因此，对于 N=1..10 和 O 符号复杂度的结果，您应该检查您的结果与 O 模型的相关性“有多好”(如果您可以为满足您的结果的 O 符号公式选择数字)。如果你不能得到数字，你需要更多的数字来获得更广泛的图片或者......好吧，你可能有错误的复杂性估计:-)。

有用的链接:

• Brief review on algorithm complexity.
• Time complexity catalogue
• Really good point to start - 寻找基于代码的示例作为输入。