big-o - 具有正常数的 Big-O

Question

在这个 Big-O / 计算复杂性问题中，假设 a 和 b 是大于 1 的正常数，并且 n 是可变参数。

我假设 a ⁿ⁺¹ = O( an ⁿ ) ， a ^bn = O( an ⁿ ) & a ^n+b = O( ^{an n} )

首先，我需要知道我的假设是否正确。

如果是这样，我将如何证明 f(n) = O(f(n))。

Answer 1

回想一下 big-O 的定义：

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

让 g=f, c=1 和 k=0，那么你有一个 f(n) ∈ O(f(n)) 的简单证明

类似地，从 a ⁿ⁺¹ =a⋅a ⁿ，令 f(n)=a ⁿ⁺¹ , g(n)=a ⁿ , c=a, k=0 ，再次证明 O(a ⁿ⁺¹ )=O(a ⁿ ) 是微不足道的。^{O(a n+b} )=O(a ⁿ )的证明是相同的。
O(a ^bn ) 不等于 O(a ⁿ ) 且 a,b>1，请参阅big-o notation 中的指数增长