<分区>
Possible Duplicate:
If f(n) = O(g(n)) , then is exp(f(n)) = O(exp(g(n)))
我在 Cormen 书中偶然发现了这个问题。
如果 f(n) 是 O (g(n)) 那么 2^f(n) 也是 O (2^g(n))。这是真的？我试图用限制规则来证明它，但完全卡住了。我的直觉告诉我这是错误的，但我们如何推断出这一点？
谢谢
<分区>
Possible Duplicate:
If f(n) = O(g(n)) , then is exp(f(n)) = O(exp(g(n)))
我在 Cormen 书中偶然发现了这个问题。
如果 f(n) 是 O (g(n)) 那么 2^f(n) 也是 O (2^g(n))。这是真的？我试图用限制规则来证明它，但完全卡住了。我的直觉告诉我这是错误的，但我们如何推断出这一点？
谢谢
最佳答案
不，不是。
f(n) = 2n 是 O(n)，但是 e^(2n) 是 O((e ^2)^n)，由于基数较大，明显比O(e^n)慢。
关于算法大 O 表示法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5710866/