math - 如果 f(n) = Θ(g(n))，是 2^f(n) = Θ(2^g(n))？

Question

如果 f(n) 是 Θ(g(n))，那么函数 2 ^f(n)是否总是 Θ(2 ^g(n) )？为什么或者为什么不？

Answer 1

这种说法是错误的。取 f(n) = 2n 和 g(n) = n。那么 f(n) = Θ(g(n)) 因为 2n = Θ(n)。

然而，2 ^f(n) = 2 ²ⁿ = 4 ⁿ和 2 ^g(n) = 2 ⁿ，但 4 ⁿ ≠ Θ(2 ⁿ )。你可以看到这个，因为

lim _{n → ∞} 4 ⁿ / 2 ⁿ

= lim _{n → ∞} 2 ⁿ

= ∞

希望这可以帮助！