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ⁿ

= ∞

希望这有帮助!