algorithm - 大 O 符号的指数增长

Question

我对理解以下问题有疑问。它说:

Prove that exponential functions have different orders of growth for different values of base.

在我看来，例如，考虑一个ⁿ。如果a=3，它的增长率会比a=2时大。看起来很明显。这真的是问题想要的吗？我怎样才能为此做一个正式的证明？

预先感谢您的帮助。

Answer 1

f(n) ∈ O(g(n)) 表示存在正常数 c 和 k，因此对于所有 n ≥ k，0 ≤ f(n) ≤ cg(n)。对于函数 f，c 和 k 的值必须是固定的，并且不能依赖于 n。

不失一般性地令1>a>b，并假设b^n ∈ O(a^n)。这意味着存在正常数 c 和 k，使得 0 ≤ b^n ≤ c.a^n 对于所有 n ≥ k，这是不可能的:
b^n ≤ c.a^n 对于所有 n ≥ k 意味着 (b/a)^n ≤ c 对于所有 n ≥ k
这与 lim (b/a)^n = +inf 矛盾，因为 b/a>1.

如果 1>a>b 那么 b^n ∉ O(a^n)，但是 a^n ∈ O(b^n) 所以 O(a^n)⊊O(b^n)