这里有很多关于 SO 的相关问题，但他们都询问是否编写程序来计算任意算法的复杂度（这显然是无法确定的）。我愿意对输入做以下限制：
- 算法终止
- 该算法是纯函数式的
问题是，是否可以编写一个程序来通过静态分析计算这种算法的时间复杂度？如果输入算法没有终止，则程序行为未定义（它可能会崩溃、返回谎言或无法终止）。
问问题
1738 次
3 回答
1
您不能 100% 确定您从任何技术中得到正确答案，以根据实际运行时间估算复杂性。这是因为确切的运行时间可能涉及一个非常复杂的函数，这意味着运行时间理论上可以跟随任何其他函数，而输入大小低于某个非常大的数字。当输入大小趋于无穷大时，运行时间只需要趋向于复杂度函数（一些倍数）。这假设您想要找到一个紧密的界限（它存在于许多但不是所有的算法中），而不仅仅是一个上限或下限。
但是您可以对通常应该非常准确的复杂性提出一些合理的估计。
另请注意，对于相同大小的不同输入，许多算法具有不同的运行时间。您可以尝试对相同大小的几个不同输入运行以下命令，并对结果进行平均以减轻这种情况。这也将有助于缓解可能影响运行时间的系统条件。尽管如果您不知道要用于这些情况的具体输入，您可能无法估计最坏和最好情况的复杂性（因为它们可能太少了，以至于您在传递随机数据时无法获取它们）。
这该怎么做：
记录一些足够大和足够不同大小的输入的时间（例如，您可以为大小等于 10 的不同幂的输入运行它，例如 100、1000 和 10000，这些应该足够大，可以运行至少一个几秒钟以减少数据的噪音）。让我们使用 3 个输入大小。严格来说，您只需要 2 个输入大小，但您可以使用 3 个或更多作为附加验证。
现在我们可以尝试将我们得到的这 3 个结果映射到一组复杂性中的一个，例如O(1), O(log(n)), O(sqrt(n)), O(n), O(n log n), ,等。O(n2)O(n3)
如果您尝试手动匹配它，您可以将获得的运行时间与上述每个函数的图表（适当缩放）一起放在图表上，然后查看哪个最匹配。
如果您尝试使其自动化，您可以尝试将每个函数映射到输入大小并查看它匹配的接近程度。
有更好的方法可以做到这一点，但一种非常简单的方法如下：
假设您有以下运行时间：
input size running time
100 21 seconds
1000 29 seconds
10000 40 seconds
现在您可以尝试将其中一个（比如最大的一个，这可能是最准确的）与上述函数之一的倍数相匹配。
O(n): k x n = k x 10000 = 40, k = 40 / 10000 = 0.004
O(log n): k x log n = k x log 10000 = 40, k = 40 / log 10000 = 10
O(n²): k x n² = k x 10000² = 40, k = 40 / 10000² = 0.0000004
现在将等式给出的内容与其他输入大小的实际运行时间进行比较：
For n = 1000, actual running time = 29 seconds
O(n): 0.004 x 1000 = 4 seconds
O(log n): 10 x log 1000 = 30 seconds
O(n²): 0.0000004 x 1000² = 0.4 seconds
For n = 100, actual running time = 21 seconds
O(n): 0.004 x 100 = 0.4 seconds
O(log n): 10 x log 100 = 20 seconds
O(n²): 0.0000004 x 100² = 0.004 seconds
看看这个，我们可以清楚地看到这O(log n)是最接近的，在这两种情况下，实际运行时间和预测运行时间仅相差 1 秒。所以这将是我们对复杂性的猜测。
于 2013-01-04T19:39:20.087 回答
1
我终于问对了地方，得到了答案。不。
于 2013-01-04T22:17:56.597 回答
0
鉴于算法停止的限制，它是可能的。为每个可能的输入执行算法并测量执行时间。接下来，选择一个函数作为可能的上限，并针对每个结果对其进行测试。如果不够好，增加边界并重新测试。重复直到边界足够好。
编辑：这个解决方案假设一个真正的计算机程序的边界，即不同输入的数量不是无限的。否则，不可能计算通用算法的复杂度。考虑复杂度为 的算法O(n) = nO(n-1)。由于输入是无限的，您将无法找到任何f可以限制复杂性的函数。
于 2012-11-14T05:49:06.257 回答