找到尽可能紧的边界？

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. 

这是事实，但我不明白什么是尽可能紧密找到边界的含义是什么？ 任何人都可以解释吗？

Answer 1

尽可能紧密意味着寻找函数g(n)与最小顺序生长，使得它仍然满足f(n) = O(g(n))。在你的例子中，它是相对简单的（因此你的困惑，我相信） - 只删除除了增长最快的术语（2^n）之外的所有东西。

但是让我们考虑一个例子，其中最严格的约束可能不会立即明显 - 斐波那契序列发生器：f(n) = f(n - 1) + f(n - 2)。一个简单的方法来找到一个上限将是使一个近似值，用n - 1更换n - 2给f(n) ≈ 2 * f(n - 1)，这是O(2^n)。这不是紧界虽然 - 通过求解一元二次方程，你会发现，最严格的约束其实Ө(1.61...^n) - 见this page了解更多详情。