algorithm - 能否通过分析其性能以编程方式找到算法的 bigO？

Question

请注意，我没有“问题”，我也不是在寻找“另一种方法来找到我的算法的大 O”。

我想知道的是，是否有可能编写一个程序，您将向其传递数据点，这些数据点都是针对各种输入大小的算法的性能测量值:(n, time taken to to解决 n) 的问题，然后这将决定您的算法的复杂性。

例如，输入可能是这样的(它可能更大，这实际上只是一个例子，这不是问题的重点):

    36 000 took 16 ms
   109 000 took 21 ms
   327 000 took 68 ms
   984 000 took 224 ms
 2 952 000 took 760 ms
 8 857 000 took 2305 ms
26 571 000 took 7379 ms
79 716 000 took 23336 ms

使用这种数据，是否有可能编写一个程序来判断我们是否有，比如说，O(n)，log(n)， n log(n) 还是 n! 算法？

Answer 1

您要找的是Curve fitting .我所知道的解决这个问题的所有简单算法都会尝试将数据点拟合成某种多项式，但我怀疑也有一些算法能够区分多项式和非多项式。