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」として知られる定数に収束することがわかります。テーブルの最後のエントリからべき乗則（T（N）= a * N ^ b）にN、T（N）、およびbを代入すると、「a」が得られます。あなたの場合、倍数比のlog4は1.555に収束するので、それは「b」です。

あなたはCourseraの「アルゴリズム、パートI」コースを受講していると思います（私と同じように）。次に、このスレッドが利用可能である必要があります。

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

サンプルセット全体について、2つのサンプルごとの傾きを計算できます。次に、これを再帰的に実行できます（勾配の勾配）。それはあなたに与えるはずです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ドライブのバージョンです...

于 2016-01-27T01:37:15.670 に答える