Clever Geek Handbook

Calculate execution time using samples

Suppose you run your program as function N and create the following table:

        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

Estimate the order of growth of the running time as a function of N. Suppose that the running time obeys the power law T (N) ~ a N ^ b.

+3


source to share


5 answers


Your N are all sequential powers 4. Taking the logarithm of the four bases of sequential time relationships, you will see that they converge to some constant known as "b". When you plug the N, T (N), and b from the last entry in your spreadsheet into the power law (T (N) = a * N ^ b), you get "a". In your case, the log4 of the temporal ratio converges to 1.555, so "b".

I am assuming you are adopting Coursera "Algorithms Part I" (as I am). Then this stream should be available to you:



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

Or you can refer to the Algorithm Analysis slides starting on page 16.

+5


source


You need to use a logarithmic graph (logN) and then take the slope of the line. This will indicate exponent b.



+2


source


You can calculate the slope between every two samples for the entire sample set. Then you can do it recursively (slope slope). This should give youb

0


source


Use Least Squares Retention Law:

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

This will give you the closest match for a and b, which you can use to extrapolate the execution time of new points.

0


source


This is more clear to me:

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

Answer: b approximately 1.55

Estimate the order in which the execution time increases depending on N. This is the google drive version ...

0


source






More articles:


All Articles