порядок роста в алгоритмах

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. Предположим, что время работы подчиняется степенному закону Т (N) ~ A N^б. Для ответа введите константу 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 

Использование логарифмов для решения.

Answer 2

1.You должен рассчитать отношение изменения роста от одной строки к одному следующему соотношению изменения в

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

2.Calculate для N

43046721/14348907 = 3 
129140163/43046721 = 3 

поэтому скорость изменения для N является 3.

отношения изменения в 3.Calculate за секунды

74.99/13.58 = 5.52 

Теперь проверить соотношение между еще одной Парой строк, чтобы быть уверенным

414.2/74.99 = 5.52 

так отношение Изменения за секунды 5,52

4.Build следующего езда

3^b = 5.52 
b = 1.55 

Наконец, мы получаем, что порядок роста времени работы составляет 1,55.