big-o - 找到尽可能严格的界限？

Question

2^n −8 = O(2^n)
It says there are some positive constants c and n0 for which
0 <= f(n) <= cg(n) for all n >= n0

我将其解决为：

2^n −8 <= c2^n
If c = 1, and n0 = 1
1-8 <= 1*1
-7<= 1
then for all n >= n0 it remains true.

这是真的，但我不明白 Find the bounds as possible 是什么意思？谁能解释一下？

Answer 1

尽可能紧意味着找到一个g(n)具有最小增长顺序的函数，使其仍然满足f(n) = O(g(n)). 在您的示例中，它相对简单（因此我相信您会感到困惑）-只需删除除增长最快的术语（2^n）之外的所有内容。

然而，让我们考虑一个例子，其中最紧密的界限可能不会立即显而易见 - 斐波那契序列生成器f(n) = f(n - 1) + f(n - 2)：找到上限的一种简单方法是进行近似，将 替换n - 2为n - 1给出f(n) ≈ 2 * f(n - 1)，即O(2^n)。虽然这不是最严格的界限 - 通过求解二次方程，您会发现实际上是最严格的界限Ө(1.61...^n)- 有关更多详细信息，请参阅此页面。