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)可以改写为 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 步。那么它们的比率是一个常数。

但是22n和2n的比值不是常数，所以你说的不成立。