big-o - 我需要帮助证明如果 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）。

现在，我需要证明或反驳这f(n) = O(g(n))意味着2^(f(n)) = O(2^g(n)))。直观地说，这是有道理的，所以我想我可以借助前面的定理来证明它。我注意到f(n)可以重写为just lg(2^f(n))，这让我很兴奋......这是我想要证明的双方的 log base 2，它简化了很多事情！g(n)lg(2^g(n))

但我很确定这行不通。仅仅因为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 ⁿ的比例不是一个常数，所以你说的不成立。

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

Answer 3

对于任何 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) 不可能为真。