使用样本计算运行时间

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)~n N ^ b.

Answer 1

你的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页开始的"算法分析"幻灯片.