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

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

我想知道的是，是否有可能编写一个程序，让您将数据点传递给所有输入大小(即(n,time taken to solve problem for 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!算法？

最佳答案

您正在寻找的是Curve fitting。我知道的所有解决此问题的简单算法都将尝试使数据点适合某种多项式，但是我怀疑有些算法也能够区分多项式和非多项式。

关于algorithm - 是否可以通过分析性能来以编程方式找到算法的bigO？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2216590/