2

假设您将程序时间作为 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) ~ a N^b。对于你的答案，输入常数 b。如果您的答案在目标答案的 1% 以内，则您的答案将被标记为正确 - 我们建议在小数分隔符后使用两位数，例如 2.34。

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

4

2 回答 2

8

嗯，这是一个简单的数学问题。

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

使用对数求解。

于 2013-10-06T09:21:45.090 回答
3

1.你应该计算从一排到下一排的增长变化比率

N          seconds  
--------------------
14348907    13.58   
43046721    74.99   
129140163   414.2   
387420489   2287.85

2.计算N的变化率

43046721 / 14348907 = 3
129140163 / 43046721 = 3

因此 N 的变化率为 3。

3.计算秒数的变化率

74.99 / 13.58 = 5.52

现在让我们检查另一对行之间的比率以确保

414.2 / 74.99 = 5.52

所以变化的秒数比率是 5.52

4.建立以下方程式

 3^b = 5.52
 b = 1.55

最后我们得到运行时间的增长顺序是1.55。

于 2015-02-06T01:16:27.313 回答