我需要帮助证明如果f(n)= O(g(n))意味着2 ^(f(n))= O(2 ^ g(n)))

Question

在之前的一个问题中,我展示了(希望是正确的)f(n)= O(g(n))意味着具有充分条件的lg(f(n))= O(lg(g(n)))(例如,lg) (g(n))> = 1,f(n)> = 1,并且n)足够大.

现在,我需要证明OR反驳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都是正面的".

Answer 1

嗯,开始时甚至都不是这样.

假设算法A需要2n步,算法B需要n步.然后他们的比例是一个常数.

但是2 ²ⁿ和2 ^n的比例并不是一个常数,所以你所说的并不成立.

Answer 2

如果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(n)))