algorithm - 如果 f(n) ∈ ω(g(n))，则 2 ^ f(n) ∈ ω(2 ^ g(n) )

Question

我必须确定以下内容是对还是错:

如果 f(n) ∈ ω(g(n))，则 2 ^ f(n) ∈ ω(2 ^ g(n) )

我计算了 f(n) = 1/n 和 g(n) = 1/n^2，得到的答案为假。

应该是:

如果 f(n) ∈ ω(g(n))，则 2 ^ f(n) ∈ Θ(2 ^ g(n) )

有人可以验证一下吗？

Answer 1

声明: f(n) ≥ g(n) ⋅ k对于所有 k ⇒ 2^f(n) ≥ 2^g(n)⋅k对于所有 k .

你的反例是正确的:1/n ≥ k/n²对所有人都是如此 k .我们可以通过限制来证明这一点:

lim<sub>n → ∞</sub> (1 / n) / (k / n²) = 1/k ⋅lim<sub>n → ∞</sub> n² / n = ∞

但是:2<sup>1/n</sup> ≥ 2<sup>1/n²<sup> ⋅ k</sup></sup>是假的。我们也可以通过限制来证明这一点:

lim<sub>n → ∞</sub> 2<sup>1/n</sup> / (2<sup>1/n²</sup> ⋅ k) = = 1/k lim of 21/n - 1/n² = = 1/k lim of 2(n - 1) / n² = 1/k ⋅ 2⁰ = = 1/k

只有当极限为无穷大时，该陈述才为真。

一个反例就足以证明一个陈述是错误的，所以你就完成了。