Мне нужна помощь в доказательстве того, что если f(n) = O(g(n)) подразумевает 2^(f(n)) = O(2^g(n)))

В предыдущей задаче я показал (надеюсь правильно), что f(n) = O(g(n)) подразумевает lg(f(n)) = O(lg(g(n))) с достаточными условиями (например, lg(g(n)) >= 1, f(n) >= 1 и достаточно большим n).

Теперь мне нужно доказать ИЛИ опровергнуть, что f(n) = O(g(n)) подразумевает 2^(f(n)) = O(2^g(n))). Интуитивно это имеет смысл, поэтому я решил, что смогу доказать это с помощью предыдущей теоремы. Я заметил, что f(n) можно переписать как lg(2^f(n)), а g(n) — это просто lg(2^g(n)), что меня взволновало... это берет логарифмическую базу 2 обеих сторон того, что я хочу доказать, и это очень упрощает!

Но я почти уверен, что это не сработает. Просто потому, что lg(2^f(n)) = O(lg(2^g(n))) не обязательно означает, что 2^f(n) = O(2^g(n))... это обратное от предыдущей теоремы (где сказано «подразумевает», а не «если и только если»).

Нужно ли мне попробовать это доказательство по-другому, или я действительно могу отказаться от того, что у меня есть (по крайней мере, для начала)?

** Говоря о других способах, может быть, я мог бы просто поспорить о том, как повышение 2 до некоторого g(n), которое «выше» f(n), все равно будет держать его выше? Это почти похоже на аргумент здравого смысла, но, возможно, я упускаю что-то важное.

**Ой, ой! Я забыл добавить, что f(n) и g(n) асимптотически положительны. Согласно определению из нашего учебника, это означает, что они «положительны для всех достаточно больших n».


big-o logarithm proof
person norman    schedule 11.09.2012    source источник

Ответы (3)


arrow_upward
13
arrow_downward

Ну, это даже неправда для начала.

Допустим, алгоритм A выполняет 2n шагов, а алгоритм B — n шагов. Тогда их отношение является константой.

Но отношение 22n и 2n не является константой, поэтому то, что вы сказали, неверно.

person user541686    schedule 11.09.2012
comment
Я не уверен, что понимаю, что вы здесь говорите. Как отношение времени выполнения двух алгоритмов, являющееся постоянным, связано с тем, ограничивает ли/как один другой? - person norman; 11.09.2012
comment
@nicole: Когда вы говорите f(n) = O(g(n)) вы имеете в виду (по определению) ограничение f(n)/g(n) при стремлении n к бесконечности есть некоторая конечная константа c. Если константа бесконечна, то (по определению) утверждение неверно. В вашем случае, если у вас есть f (n) = 2n и g (n) = n, тогда f (n) = O (g (n)), но 2 ^ (2n) не O (2 ^ n), потому что отношение бесконечно. - person user541686; 11.09.2012
comment
Ах! Мы действительно обсуждали эту теорему на лекции, но я забыл о ней. Итак, я думаю, мы могли бы сказать, что 2 ^ 2 n/2 ^ n = 2 ^ n, что не дает нам хороший, конечный предел. Спасибо! - person norman; 11.09.2012
comment
@Mehrdad - но если алгоритм A выполняет 2n шагов, а B - n шагов, верно ли, что A = O (B), что является предположением, данным в задаче? Моя интерпретация такова: A = O(B) подразумевает, что B растет быстрее, чем A, и в этом случае интуитивно очевидно, что это утверждение верно (поскольку 2^x монотонно возрастает по x). Но не является ли мое предположение чрезмерным упрощением? - person drew moore; 21.01.2015
comment
@drewmoore: Нет причин, по которым B растет быстрее, чем A, или что A растет быстрее, чем B, так же правильно говорить n = O (2n), как и 2n = O (n). Однако по соглашению аргумент O лишен констант, поскольку 2n = O(n) легче понять. - person user541686; 21.01.2015
comment
@Mehrdad: И это просто потому, что мы игнорируем коэффициенты в асимптотической записи, верно? Если бы гипотетически мы этого не сделали, то НЕ было бы истинным, что 2n = 0(n), потому что 2n растет быстрее, чем n. Но поскольку мы игнорируем коэффициент и просто рассматриваем 2n и n как функции 1-й степени, приведенный вами пример возможен. Верный? - person drew moore; 21.01.2015
comment
@drewmoore: я не уверен, на какой пример вы ссылаетесь, но да, это потому, что мы игнорируем константы. - person user541686; 21.01.2015
comment
@Mehrdad - Спасибо! Позвольте мне задать этот вопрос лучше: если предположить, что f(n) = o(g(n)) (маленькое o, а не большое O), то БЫЛО бы верно, что 2^f(n) = O(2 ^g(n)), потому что в этом случае мы знали бы, что время выполнения g(n) строго больше, чем время выполнения f(n), а не просто ›= — верно? - person drew moore; 21.01.2015
comment
@drewmoore: Ну да, если f(n)/g(n) -> 0 при n -> бесконечность, то это подразумевает f(n) ‹ g(n) для больших n, что означает 2^f(n) ‹ 2^ g(n) для больших n, поэтому, безусловно, также верно, что 2^f(n) ‹= 2^g(n), что подразумевает 2^f(n) = O(2^g(n)). - person user541686; 21.01.2015
comment
@Mehrdad Могу я тебя кое о чем спросить? Как мы можем найти функции f(n) такие, что f(n)=O(f(n)^2) ? - person Mary Star; 27.02.2015
comment
@evinda: вы хотите f(n)/f(n)^2 = c (некоторая константа), это означает 1/f(n) = c или f(n) = 1/c, так что это означает f(n) должно быть константой. - person user541686; 27.02.2015
comment
@Mehrdad Я смотрю на упражнение: докажите или не одобрите, если f (n) = O (f (n) ^ 2). Могу ли я ответить следующим образом? Пусть f(n)=1/n для всех n из N. Предположим, что f(n)=O(f(n)^2). Это означает, что существуют c›0 и n_0 в N такие, что 1/n=f(n)‹= c f(n)^2=c(1/n^2) для всех n›= n_0. 1/n ‹=c (1/n^2) =› n^2/n ‹=c=› n ‹= c, противоречие. - person Mary Star; 27.02.2015
comment
@Mehrdad Мы замечаем, что f(n) в O(f(n)^2) тогда и только тогда, когда существуют c›0, n_0 в N такие, что для всех n›=n_0: f(n) ‹= c f(n)^2 =›(f(n) !=0) 1 ‹=c f(n) =› f(n) \geq 1/c:=C =›f(n) в Ω(1). - person Mary Star; 27.02.2015
comment
@evinda: Извините, я не буду исправлять вашу домашнюю работу за вас. Я только что привел вам доказательство того, что этому условию удовлетворяют только те f, которые должны быть постоянными, так что этого должно быть достаточно. - person user541686; 27.02.2015

arrow_upward
10
arrow_downward

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

Пусть f(n) = 2log n и g(n) = log n
(предположим, что log соответствует основанию 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( п)))

person Mohit Arvind khakharia    schedule 28.02.2017
comment
Благодарю вас! Мне очень помог! - person Dmytro Lopushanskyy; 27.09.2020

arrow_upward
2
arrow_downward

Для любых f,g: N->R*, если f(n) = O(g(n)) то 2^(f(n) = O(2^g(n)) (1)

Мы можем опровергнуть (1), найдя контрпример.

Предположим, что (1) верно -> по определению Big-O существует c>0 и целое число m >= 0 такое, что:

2^f(n) ‹= c2^g(n) , для всех n >= m (2)

Выбираем f(n) = 2n, g(n) = n, также имеем f(n) = O(g(n)), применяем их к (2).

-> 2^(2n) <= c2^n -> 2^n <= c (3)

Это означает: существует c>0 и целое число m >= 0 такое, что: 2^n ‹= c для всех n >= m.

Такого c не существует, потому что если оно есть, мы всегда находим n > lg(c), что делает (3) неверным: 2^n >= c для всех n >= lg(c).

Следовательно, (1) не может быть верным.

person Tuan Le PN    schedule 12.11.2019