大O符號的數據結構

Question

我有關於大O符號 的方程

f(n)=3n+8 

我們怎麼找到的上界以及我們如何找到大O表示法無疑 給出的解決方案是

3n+8<=4n和n>8，其中c=4和n_0=8

我不知道這個解決方案是如何發現的。你能解釋一下如何解決這個問題嗎？從CLRS大哦符號的

Answer 1

數學定義：

O(g(n)) = { f(n) : there exists positive constants c and n_0 such that 0 <= f(n) <= c.g(n) for all n >= n_0 } 

讓f(n)=3n+8。

然後，我們必須找到正的常數c和n_0，使得0 <= 3n+8 <= c.g(n) for all n >= n_0。

讓g(n)=n。 （如果你願意，可以試試各種功能）

然後，0 <= 3n+8 <= cn for all n >= n_0。只有當c的值大於3和n值大於或等於8

這個表達式將保持爲真。如果情況並非如此，那麼這種線性不等式將失敗。例如：

• 如果c = 3，那麼我們將得到0 <= 3n+8 <= 3n這是錯誤的。
• 如果c = 4和n_0 = 7，那麼我們將得到0 <= 3n+8 <= 4n，這意味着0 <= 3.7+8 <= 4.7，它給出0 <= 29 <= 28，這又是錯誤的。

因此，我們可以得出結論f(n) = O(n) for c = 4 and n_0 = 8。

This是一個很好的資源，如果你想了解更多。