这里有很多关于SO的相关问题，但它们都是关于编写一个程序来计算任意算法的复杂性(这显然是不确定的)。我愿意对输入进行以下限制：
- 算法终止
- 该算法是纯函数的
问题是，是否可以编写一个程序来通过静态分析计算这种算法的时间复杂性？如果输入算法没有终止，则程序行为是未定义的(它可能崩溃、返回谎言或无法终止)。
我终于问对了地方，得到了答案。编号
https://cstheory.stackexchange.com/questions/14969/algorithmically-compute-a-reasonable-bound-on-the-runtime-of-an-algorithm#comment40524_14969
你不可能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秒。因此，这将是我们对复杂性的猜测。
给定算法停止的限制，这是可能的。为每个可能的输入执行算法，并测量执行时间。接下来，选择一个函数作为可能的上边界，并对每个结果进行测试。如果不够好，增加边界并重新测试。重复，直到边界足够好。
编辑：这个解决方案假设了真实计算机程序的边界，即不同输入的数量不是无限的。否则，就不可能计算通用算法的复杂性。考虑复杂度为O(n) = nO(n-1)的算法。由于输入是无限的，您将无法找到任何可以绑定复杂性的函数f。