算法增长的顺序

Question

假设您将程序计时为N的函数并生成下表.

        N   seconds
-------------------
    19683      0.00
    59049      0.00
   177147      0.01
   531441      0.08
  1594323      0.44
  4782969      2.46
 14348907     13.58
 43046721     74.99
129140163    414.20
387420489   2287.85

估计作为N的函数的运行时间的增长顺序.假设运行时间服从幂律T(N)~n N ^ b.要获得答案,请输入常数b.如果答案在目标答案的1%范围内,您的答案将被标记为正确 - 我们建议在小数分隔符后使用两位数,例如2.34.

有人可以解释如何计算吗？

Answer 1

嗯,这是一个简单的数学问题.

I : a*387420489^b = 2287.85 -> a = 387420489^b/2287.85
II: a*43046721^b  =  74.99  -> a = 43046721^b/74.99
III: (I and II)-> 387420489^b/2287.85 = 43046721^b/74.99 ->
-> http://www.purplemath.com/modules/solvexpo2.htm

使用对数来解决.