3

假设您将程序时间作为 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) ~ a N^b。

4

5 回答 5

5

你的 N 都是 4 的连续幂。以 4 为基础的对数的连续比率，你会看到它们收敛到某个常数，称为“b”。当您将表格最后一项中的 N、T(N) 和 b 替换为幂律 (T(N) = a * N ^ b) 时，您将得到“a”。在您的情况下，倍率的 log4 收敛到 1.555，所以这就是“b”。

我猜你正在学习 Coursera 的“算法，第一部分”课程（就像我一样）。然后，这个线程必须对你可用：

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

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

于 2013-02-12T05:36:33.803 回答
2

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

于 2013-02-11T18:24:51.650 回答
0

您可以计算整个样本集的每两个样本之间的斜率。然后您可以递归地执行此操作（斜坡的斜率）。那应该给你b

于 2013-02-11T18:31:48.360 回答
0

使用最小二乘拟合幂律：

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

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

于 2013-02-11T19:09:13.410 回答
0

对我来说，这样更清楚：

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 的函数。 这是 google drive 版本...

于 2016-01-27T01:37:15.670 回答