使用样本计算运行时间

Question

假设您将程序计时为N的函数，并生成下表：

        N   seconds
-------------------
     4096      0.00
    16384      0.01
    65536      0.06    
   262144      0.51   
  1048576      4.41   
  4194304     38.10  
 16777216    329.13  
 67108864   2842.87

估计运行时间作为N的函数的增长顺序。假设运行时间服从幂律T（N）~aN^b。

Answer 1

你的N都是4的连续幂。取连续时间比率的4基对数，你会看到它们收敛到某个常数，即"b"。当你用幂律（T（N）=a*N^b）代替表最后一项中的N、T（N）和b时，你会得到"a"。在你的例子中，log4的倍数比收敛到1.555，所以这是"b"。

我猜你正在参加Coursera的"算法，第一部分"课程（和我一样）。那么，这个线程一定可以为你使用：

https://class.coursera.org/algs4partI-002/forum/thread?thread_id=149

或者，您可以参考从第16页开始的"算法分析"幻灯片。

Answer 2

您需要使用对数图（logN），然后取直线的斜率。这将指示指数b。

Answer 3

您可以计算整个样本集每两个样本之间的斜率。然后可以递归地执行此操作（斜率）。这将为您提供b

Answer 4

使用最小二乘拟合幂律：

http://mathworld.wolfram.com/LeastSquaresFittingPowerLaw.html

这将为a和b提供最接近的拟合，然后可以用来推断新点的运行时间。

Answer 5

对我来说，这一点更清楚：

N           seconds     log(N, 2)   log(seconds, 2)  Y(n)-Y(n+1)/
                            or X     or Y            X(n)-X(n+1)
----------------------------------------------------------------------------
4096              0         12      #NUM!
16384          0.01         14      -6.64385619         1.29248125
65536          0.06         16      -4.058893689        1.543731421
262144         0.51         18      -0.9714308478       1.556104752
1048576        4.41         20      2.140778656         1.555470218
4194304        38.1         22      5.251719093         1.555397315
16777216     329.13         24      8.362513723         1.555309345 
67108864    2842.87         26      11.47313241

答案：b大约是1.55

估计运行时间的增长顺序作为N的函数。这是谷歌驱动器版本。。。