Если F(п) = о(г(N)), тогда 2^(ф(п)) = о(2^(г(N)))?

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

EDIT: рад, что я поднял дискуссию :) предположим f, g > 0 для простоты

3 3
computer-science asymptotic-complexity

3 ответа:

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

Набросок доказательства:

Prerequsites: г(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 

(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)

Потому что g (n) - > pos. бесконечность. для n - > pos. бесконечность. существует 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) 0 для всех вещественных x, следует 

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

Q. e. d.

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

EDIT: некоторые мысли о других 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)

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))).

1

Простое доказательство на примере,

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

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

Мы знаем, 2log 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)))

-1