自动计算终止算法的算法时间复杂度

Question

在SO上有很多相关的问题，但是它们都询问如何编写一个程序来计算任意算法的复杂度(这显然是不可决定的)。我愿意对输入做出以下限制：

1. 算法终止
2. 算法完全是函数式的

问题是，能否编写一个程序通过静态分析计算这种算法的时间复杂度？如果输入算法不终止，则程序行为是未定义的(可能会崩溃、返回错误或无法终止)。

- singpolyma

---

你能编辑一下并提出一个可以回答的问题吗？我看到了需求陈述，但没有实际的问题。 - Ken White

@KenWhite，问题在标题中，但我已经更新了内容，以便更清楚地表达。 - singpolyma

我在标题中读到了一句话（完全没有问题）。现在你实际上在问什么就清楚多了。谢谢，加一。 - Ken White

Answer 1

我在正确的地方询问了问题，并得到了答案。不。

链接：https://cstheory.stackexchange.com/questions/14969/algorithmically-compute-a-reasonable-bound-on-the-runtime-of-an-algorithm#comment40524_14969

- singpolyma

Answer 2

无论使用任何基于实际运行时间的技术来估计复杂度，您都无法百分之百确定您得到了正确的答案。这是因为确切的运行时间可能涉及一个非常复杂的函数，意味着在输入大小低于某个非常非常大的数字时，运行时间理论上可以遵循任何其他函数。当输入大小趋近于无穷大时，运行时间只需要趋向于（某个倍数的）复杂度函数。这假设您想要找到一个紧密边界（对于许多算法而言存在，但并非所有算法都存在），而不仅仅是上限或下限。

但是，您可以提出一些合理的复杂度估计，这通常应该相当准确。

还要注意，许多算法对于相同大小的不同输入具有不同的运行时间。您可以尝试对相同大小的几个不同输入运行以下操作，并对结果进行平均以减轻这种情况。这也有助于减轻可能影响运行时间的系统条件。虽然如果您不知道用于那些最坏和最好情况的特定输入（因为它们可能太罕见而无法通过随机数据传递它们）时，您可能无法估计最坏和最好情况的复杂度。

如何做到这一点：

记录一些足够大且大小不同的输入的时间（例如，您可以运行大小等于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秒。因此，这将是我们对复杂性的猜测。

- Bernhard Barker

Answer 3

考虑到算法停止的限制，我们可以对每个可能的输入执行算法并测量执行时间。然后，选择一个函数作为可能的上界，并对每个结果进行测试。如果不够好，就增加边界并重新测试。重复此过程，直到边界足够好。

编辑：此解决方案假定实际计算机程序的边界是有限的，即不同输入的数量不是无限的。否则，无法计算一般算法的复杂度。考虑复杂度为O(n) = nO(n-1)的算法。由于输入是无限的，您将无法找到任何可以限制复杂度的函数f。

- SomeWittyUsername

---

为什么不满意？这个问题纯粹是理论上的，答案也一样。我想它可能可以优化，但我看不出有必要这样做。 - SomeWittyUsername

就我个人而言，我会发现实际解决方案有价值——你能想象编译器警告关于无意中使用n**3算法的情况吗？但作为理论答案，它仍然存在一些不足之处，即在寻找边界函数的启发式方法中。尽管如此，这种设置并没有提供太多改进的动力，我承认这一点。 - Jamey Sharp

我认为确定一个通用算法是否受O(n3)限制，需要至少进行O(n3)次计算，无论是在编译时还是运行时 - 我认为在正常情况下任何一种方式都不可接受。 - SomeWittyUsername

这个解决方案在大多数终止输入上不太可能终止（因为通常存在无限数量的可能输入），而且也不是非常严谨，主要是启发式的。 - singpolyma

@icepack 真正的计算机程序始终具有无限不同的可能输入。例如，您如何计算查找链表长度的算法的运行时间？ - singpolyma