algorithm - 函数的 big-O 可以比函数本身大吗？

Question

假设两个(正)非递减函数 f 和 g 使得 f(n)=O(g(n))。 是 2^f(n)=O(2^g(n)) 吗？

方案中给出了2种情况:

1. 假设 f(n) = g(n) = n，在这种情况下它们是相等的，我完全理解。
2. 对于第二种情况，作者假设让 f(n) = 10n 和 g(n) = n，这个假设是否正确？函数的大 O 怎么可能比函数本身大？

我在这里错过了一个关键点？

提前致谢。

Answer 1

首先观察10n=O(n)根据定义。如果您不清楚，请重新阅读 big-O 的定义。符号。

然而，2^(10n)不是 O(2^n)因为这意味着

2^(10n) <= C2^n

对于一些常量 C和 n 的所有值高于某个阈值 N .

要了解为什么这不是真的，请选择一些常量 D这样 C <= 2^D (例如，D = lgC)。我们得到

2^(10n) <= C2^n <= (2^D)(2^n) = 2^(D+n)

暗示

10n <= D + n

或

9n <= D

对于 n 的所有值高于阈值 N .但这是不可能的，因为 D是常数并且 9n是无界的。

总而言之，我们有一个断言的反例 2^f(n) = O(2^g(n))因此它通常不成立。