Если f(n) = o(g(n)), то есть 2^(f(n)) = o(2^(g(n)))?

Question

Обратите внимание, что я спрашиваю о маленьком о здесь (см. Аналогичный вопрос здесь) - для большого О, это явно неправильно - для маленького - это кажется правильным, но, кажется, не могу доказать это...

РЕДАКТИРОВАТЬ: рад, что я поднял дискуссию:) Предположим, f,g > 0 для простоты

Answer 1

Это, по крайней мере, если g (n) сходится к положительной бесконечности для n к положительной бесконечности (если g (n) нет, легко найти контрпримеры).

Эскиз доказательства:

Предварительные условия: g(n) сходится к положительной бесконечности для n к положительной бесконечности.

f (n) в o (g (n)) означает:

for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).

Форма следующая:

2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).

Для eps < 1:

(2^eps)^n is in o(2^n) (as 2^eps < 2) 

Отсюда следует, что для каждого eps2 > 0 существует n1, поэтому для всех n > n1

(2^eps)^n < eps2*(2^n).

Выбор eps2 = eps vields:

(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)

Потому что г (п) -> поз. инф. для п -> поз. инф. существует n2, так что

g(n) > n1 for all n > n2

Исходя из есть

(2^eps)^g(n) < eps*2^g(n) for all n > n2.

Таким образом, для каждого 0 = max (n0, n2), так что

2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.

Для каждого eps3> 1 также:

2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)

Таким образом, для каждого eps> 0 существует n3, так что

2^abs(f(n)) < eps*2^g(n) for all n > n3

Поскольку 2^f(n) < 2^abs(f(n)) для всех n, и 2^x > 0 для всех вещественных x, следует

abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3

QED

Если что-то неясно или неправильно, пожалуйста, прокомментируйте.

РЕДАКТИРОВАТЬ: Некоторые мысли о других g(n):

Подпоследовательность g (n) ограничена, то есть существует некоторый x, так что не существует n0 с abs(g(n))>=x для всех n> n0:

o (g (n)) состоит только из функций, которые постоянны 0 после некоторого n или сходятся к 0. Тогда 2^g(n) также имеет ограниченную подпоследовательность, но 2 ^ f (n) постоянна 1 после некоторой точки.

Не существует n0, поэтому g (n)> 0 для всех n> n0:

2^g(n) <1, если g (n) <0, поэтому g (n) имеет ограниченную подпоследовательность, означающую, что o(2^g(n)) состоит только из функций, которые являются постоянными 0 после некоторого n или сходятся к 0,

Answer 2

Вот ответ. Результат зависит от свойств сходимости g(n).

Сначала рассмотрим связанный лимит:

lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
lim(x->inf) ( log_2(2^(f(n))) - log_2(2^(g(n))) )
=
lim(x->inf) ( f(n) - g(n) ) = lim(x->inf) ( g(n) * f(n) / g(n) - g(n) )
=
lim(x->inf) ( -g(n) ) = - lim(x->inf) g(n)

... Теперь, чтобы получить это в форме исходного вопроса в вашем посте, ЕСЛИ математически правильно переключать лимит и журнал (что я думаю, что это так), то мы бы получили:

lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) / (2^(g(n)))).

Теперь переходим к ответу на вопрос. Если это правда, что

2^(f(n)) = o(2^(g(n))),

тогда в пределе правая часть становится

log_2 (0) = - inf

... так что в этом сценарии должно быть верно, что

lim(x->inf) g(n) = inf

Этот результат, кажется, имеет смысл. Рассматривать f(x) = exp(-x) and g(x) = 1 - exp(-x), Понятно, что в этом примере f(x) = o(g(x)), Тем не мение, 2^(f(x)) is not o(2^(g(x))) так как

lim(x->inf) (2^exp(-x)) / (2^(1-exp(-x))) = 1/2.

Но учитывая f(x) = exp(x), g(x) = exp(2x) где также f(x) = o(g(x)) и где lim(x->inf) g(x) = inf, соблюдая вышеуказанное условие, имеем

lim(x->inf) (2^exp(x)) / (2^exp(2x))
=
lim(x->inf) 1 / 2^(exp(x)*(exp(x) - 1)) = 0

так 2^(f(x)) = o(2^(g(x))),

Answer 3

Легко Доказательство с примером,

Если f (n) = O (g (n)),
2 ^ (f (n)) не равно O (2 ^ g (n)))

Пусть f (n) = 2log n и g (n) = log n
(Предположим, лог находится на базе 2)

Мы знаем, 2log n <= c(log n), поэтому f (n) = O (g (n))

2 ^ (f (n)) = 2 ^ log n ^ 2 = n ^ 2
2 ^ (g (n)) = 2 ^ log n = n

Мы знаем это
n ^ 2 это не O (n)

Следовательно, 2 ^ (f (n)) не равно O (2 ^ g (n)))