找到儘可能緊的邊界？

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瞭解更多詳情。