我需要帮助证明如果f(n)= O(g(n))意味着2 ^(f(n))= O(2 ^ g(n))) [英] I need help proving that if f(n) = O(g(n)) implies 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).

In a previous problem, I showed (hopefully correctly) that f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))) with sufficient conditions (e.g., lg(g(n)) >= 1, f(n) >= 1, and sufficiently large 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的基础，简化了很多事情！

Now, I need to prove OR disprove that f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n))). Intuitively, this makes sense, so I figured I could prove it with help from the previous theorem. I noticed that f(n) can be rewritten as lg(2^f(n)) and that g(n) is just lg(2^g(n)), which got me excited...this is taking the log base 2 of both sides of what I want to prove, and it simplifies things a lot!

但是我很确定这是行不通的.只是因为lg(2^f(n)) = O(lg(2^g(n)))不一定表示2^f(n) = O(2^g(n)) ...，所以它比前一个定理(表示隐含"，而不是仅当且仅当")倒退.

But I'm pretty sure this won't work. Just because lg(2^f(n)) = O(lg(2^g(n))) does not necessarily mean that 2^f(n) = O(2^g(n))...that's backwards from the previous theorem (which said "implies", not "if and only if").

我是否需要以其他方式尝试该证明，或者我是否可以实际使用我现有的东西(至少作为入门者)?

Do I need to try this proof another way, or can I actually go off of what I have (at least as a starter)?

**说到其他方式，也许我可以争论一下如何将2提升到某个f(n)上方的某个g(n)仍将其保持在更高的水平?几乎感觉像是一个常识性的争论，但也许我错过了一些重要的事情.

**Speaking of other ways, maybe I could just argue about how raising 2 to some g(n) that is "above" an f(n) will still keep it higher? It almost feels like a common sense argument, but maybe I'm missing something important..

**哦，天哪！我忘了补充说f(n)和g(n)是渐近正的.根据我们的教科书定义，这意味着它们对于所有足够大的n都是正值".

**Oh, oops! I forgot to add that f(n) and g(n) are asymptotically positive. By our textbook definition, this means that they are "positive for all sufficiently large n."

推荐答案

好吧，它甚至都不是真的.

Well, it's not even true to begin with.

比方说，算法A采取2n步，而算法B采取n步.那么它们的比率就是一个常数.

Let's say algorithm A takes 2n steps, and algorithm B takes n steps. Then their ratio is a constant.

但是2 ²ⁿ 和2 ⁿ 之比不是常数，所以您所说的不成立.

But the ratio of 2²ⁿ and 2ⁿ is not a constant, so what you said doesn't hold.

这篇关于我需要帮助证明如果f(n)= O(g(n))意味着2 ^(f(n))= O(2 ^ g(n)))的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！