計算使用運行時間樣本

假設你時間的節目作爲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。

來源

2013-02-11 Mohamed Naguib

什麼是孤獨的'1'在'線38.10' 4194304幹什麼？ – nhahtdh 2013-02-11 18:23:54

@nhahtdh對不起，我修改了它:) – 2013-02-11 18:24:33

擺脫第一點......它低於計時器的分辨率。 – thang 2013-02-11 19:45:11

你的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-12 05:36:33

感謝您的答案，但我真的無法從講座:) – Adelin 2015-09-14 08:25:09

您需要使用對數圖（logN），然後取斜線。這將表明指數b。

來源

2013-02-11 18:24:51

您可以計算整個樣本集的每兩個樣本之間的斜率。然後您可以遞歸地執行此操作（斜率斜率）。這應該給你b

來源

2013-02-11 18:31:48 noMAD

使用最小二乘法擬合冪律：

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

這會給你最接近適合a和b，然後您可以用它來推斷的新點運行。

來源

2013-02-11 19:09:13 argentage

開始對我來說，這種方式更加清晰：

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

Estimate the order of growth of the running time as a function of N. 這是谷歌驅動版本...

來源

2016-01-27 01:37:15 freedev

計算使用運行時間樣本

回答

相關問題