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

Question

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

Answer 1

这个说法是错误的。取 f(n) = 2n 和 g(n) = n。然后 f(n) = Θ(g(n)) 因为 2n = Θ(n)。

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

lim_{n → ∞} 4ⁿ / 2ⁿ

= lim_{n → ∞} 2ⁿ

= ∞

希望这可以帮助!