Сравнение скорости роста экспоненциальной функции?

Предположим, у нас есть две функции f(n) = 22n+1 и g(n)=22n. Я хочу сравнить их темпы роста этих двух функций, используя два разных метода.

Метод первый: возьмите соотношение

Определим t(n) = f(n)/g(n). Затем

t(n) = f(n) / g(n)

= 22n+1 / 22n

= 22n + 1 - 2n

= 22н

Итак, предположим, что f(n) растет намного быстрее, чем g(n).

Метод второй: используйте логарифмы

Как и раньше, пусть t(n) = f(n)/g(n). Теперь возьмем логарифмическую базу два с обеих сторон:

lg t(n) = lg (f(n) / g(n))

= lg (22n+1 / 22n)

= lg 22n+1 - lg 22n)

= 2n+1 - 2n

Теперь возьмем основание бревна два с обеих сторон:

lg lg t(n) = (n + 1) lg 2 / n lg 2

= (n + 1) / n

Игнорируя постоянный член, мы получаем lg lg t(n) = 1, что является константой, поэтому f(n) и g(n) должны иметь одинаковую скорость роста.

Почему я получаю неправильный ответ, используя второй метод?


function algorithm time-complexity big-o asymptotic-complexity
person Atinesh    schedule 05.09.2013    source источник
comment
Этот вопрос кажется не по теме, потому что он касается математики.   -  person Paul R    schedule 05.09.2013
comment
Вы предполагаете a/b=(log a)/(log b), что в целом неверно.   -  person Reinstate Monica    schedule 01.11.2013
comment
Этот вопрос кажется не по теме, потому что он касается математики.   -  person Derek 朕會功夫    schedule 31.01.2014

Ответы (2)


arrow_upward
2
arrow_downward

Я думаю, что ваша ошибка предполагает следующее:

Если log log f(x) / log log g(x) является константой, то f(x) = (g(x)).

Вот простой контрпример. Пусть f(x) = x2 и g(x) = x. Затем

log log f(x) = log log x2 = log (2 log x) = log 2 + log log x

и

лог лог г(х) = лог лог х

Здесь log log f(x) и log log g(x) отличаются только на константу (а именно, log 2), но очевидно, что f(x) и g(x) растут с одинаковой скоростью, это неверно. Другими словами, небезопасно игнорировать константы после получения логов скорости роста двух функций.

В вашей логике есть вторая ошибка. Если вы вычислите f (n) / g (n), вы получите

22n + 1 / 22n

= 22n+1 - 2n

= 22н

Если вы возьмете журнал этого дважды, вы получите

lg lg 22н

= lg 2n

= n

Так что неверно даже то, что логарифм логарифма отношения равен (n + 1)/n; вместо этого это n, которое все еще стремится к бесконечности. Это также говорит о том, что f(n) растет намного быстрее, чем g(n).

Надеюсь это поможет!

person templatetypedef    schedule 01.11.2013

arrow_upward
2
arrow_downward

Где вы ошиблись: «игнорирование постоянного члена».

t(n) = (n+1)/n = n/n + 1/n = 1 + 1/n > 1

person Scott Hunter    schedule 05.09.2013
comment
Однако 1 + 1/n ограничено константой 2 сверху. - person templatetypedef; 01.11.2013
comment
@ Скотт Хантер Да, ты прав. Я понял, где ошибся - person Atinesh; 31.01.2014