[Algorithms] The Big-O notation




在 Computer Science 裡面,很常的我們都沒有辦法得出一個絕對的數字來表示問題的難度或複雜度。所以我們會嘗試的用簡化的界限來表示複雜度,一方面也讓我們可以更簡單的估計程式執行大約的狀況。意思大概就是讓你知道,當 n 大概很大的時候,程式執行的複雜度差不多是怎樣?!

假設 [latex]f(n)[/latex]是程式的複雜度。

[latex]f(n)=O(g(n))[/latex] (asymptotic upper bound):表示 n 夠大時,[latex]f(n)[/latex] 大致上會小於 [latex]c\cdot g(n)[/latex],其中 c 是一個正的係數。

[latex]f(n)=\Omega(g(n))[/latex] (asymptotic lower bound):表示 n 夠大時,[latex]f(n)[/latex] 大致上會大於 [latex]c\cdot g(n)[/latex],其中 c 是一個正的係數。

[latex]f(n)=\Theta(g(n))[/latex] (asymptotic tight bound):表示 n 夠大時,[latex]c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)[/latex],其中 [latex]c_1, c_2[/latex] 是正的係數。

[latex]f(n)=o(g(n))[/latex] (asymptotically smaller):當 n 變很大時,[latex]f(n)\ll g(n)[/latex]。

[latex]f(n)=\omega(g(n))[/latex] (asymptotically larger):當 n 變很大時,[latex]f(n)\gg g(n)[/latex]。

如果,用實數 a 跟 b 來類比複雜度的函數 f 跟 g ,這些符號的意思大概如下:

[latex]f(n)=O(g(n)) \approx a\leq b[/latex]
[latex]f(n)=\Omega(g(n)) \approx a\geq b[/latex]
[latex]f(n)=\Theta(g(n)) \approx a = b[/latex]
[latex]f(n)=o(g(n)) \approx a < b[/latex] [latex]f(n)=\omega(g(n)) \approx a > b[/latex]

Reference:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms, 2nd edition”, The MIT Press, 2001.




Be the first to comment

Leave a Reply

Your email address will not be published.


*


This site uses Akismet to reduce spam. Learn how your comment data is processed.