算法的bigO可以通过分析其perfs以编程方式找到吗？

Question

请注意,我没有"问题",我不是在寻找"另一种方法来找到我的算法的大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!算法中？

Answer 1

您正在寻找的是曲线拟合.我所知道的所有这个问题的简单算法都会尝试将数据点拟合成某种多项式,但我怀疑那些能够区分多项式和非多项式的算法.

Answer 2

您可以使用曲线拟合(请参阅@Max S.)来确定描述数据的公式.然而,这只是故事的一半,因为无法知道数据是否完全描述了您的算法.

例如,您的算法可能会呈现n <1,000,000,000的线性行为,然后开始以二次方式运行.如果您没有n> 1,000,000,000的数据点,那么您的分析程序将无法给出正确的答案.

因此,总结一下,您可以通过编程方式进行,但结果将仅限于样本中的数据点.并且没有算法来确定样本是否足以覆盖所有"有趣"点.

Answer 3

如果你想通过经验估计大O,你必须非常小心,以确保你在各种大小的各种实例上进行测试.请记住,大O是最坏情况的概念.寻找在几乎所有病理情况下表现良好的算法并不罕见,但正是那些确定大O时间的病理情况.也就是说,如果您错过了采样中的病态情况,您可能会认为O(2 ^ n)算法是O(n).

如果您真正需要的是大O时间,而不仅仅是平均性能的概念,那么我建议分析证明它.如果不这样做,你就不能确定你没有错过一些病理输入.