使用∈记号分析时间复杂度：f(n)∈O(g(n))是否可推出3^f(n)∈O(3^g(n))

推导逻辑说明 #

首先明确大O记号的定义：若$f(n) ∈ O(g(n))$，代表存在正的常数$C$和自然数$n_0$，当$n ≥ n_0$时，恒满足$|f(n)| ≤ C·|g(n)|$。
指数函数的增长速度对指数项的系数非常敏感，大O定义里的常数因子$C$会在指数运算后变成底数的指数，直接改变整个函数的增长量级，因此原推导不成立。 #

具体反例 #

我们可以找一个非常直观的反例验证：

• 取$f(n) = 2n$，$g(n) = n$
• 显然满足$f(n) ∈ O(g(n))$，取$C=2$、$n_0=1$就符合大O的定义要求
• 代入指数运算后：$3^{f(n)} = 3^{2n} = 9^n$，$3{g(n)} = 3^n$
• 此时$9^n / 3^n = 3^{n$，当$n$趋向于无穷时该比值也趋向无穷，不存在常数$C'$能让$9}n ≤ C'·3^{n$对所有足够大的$n$成立，因此$3}{f(n)} ∉ O(3^{g(n)})$

补充：推导成立的额外条件 #

如果除了$f(n) ∈ O(g(n))$之外，还满足*$f(n) ≤ g(n)$对所有足够大的$n$成立*，那么$3^{f(n)} ≤ 3^{g(n)}$，此时结论才成立。仅靠原有的大O条件是不够的。 #

内容的提问来源于stack exchange，提问作者bennietgek