[教學] 教你如何 輕鬆了解資料結構-Asymptotic Notation

大家好
今天要來教大家資料結構中基本的一些基本元素
就是Asymptotic Notation
它是用來表示一個程式演算法或者資料結構的動作
需要花多少時間(次數)來執行
共有六種代號
O,o,Θ,θ,Ω,ω

基於輕鬆了解
我就以常用的O,θ,Ω來做教學
詳細的定義就補充在後面留給有需要的人自行參考

O讀做大歐(big-oh)
θ讀做系打(?)(theta)
Ω讀做偶妹嘎(omega)

※Big-O Notation： O(某多項式)
定義：
代表一個操作數量最慘(最多)不超過這個函式(上界的概念)

舉例：
令f(n)=n^2
g(n)=3*n^6-10
假設有一個操作數量的圖形為f(n)

這是概念圖

你會發現
在後來的狀況下g(n) 會穩定在f(n)的函數圖形上面
因此此操作的asymptotic notation為 O(n^6)

欸???等等
為什麼不是O(3*n^6)?
→寫O(3*n^6)也是可以的，不過因為在asymptotic notation，我們只在乎多項式裡面的最高次方，所以我們就省略3不寫，因此
O(3*n^6) = O(n^6)是成立的

※Theta Notation： θ(某多項式)
定義：
代表一個操作會介於一個常數倍的多項式間(保證在一個範圍內的概念，有夾擊的感覺)

舉例：
令f(n) = n^2
g(n) = n^2+1
c1 = 0.5
c2 = 2
假設有個操作數量函式為f(n)

這是概念圖

你會發現
c1*g(n) 和 c2*g(n)可以把f(n)上下包夾起來
因此這個操作的asymptotic notation就是 θ(n^2)

從上面可以知道
如果你已經知道f(n)是多少
要求θ的話
答案就是f(n)的最高次項，因為他主導了這個函式

※Omega Notation：Ω(某多項式)
定義：
代表一個操作數量至少必大於這個函式(下界的概念)

舉例：
令f(n) = n^2
g(n) = 2n + 1
假設有個操作數量函式為f(n)

你會發現
c*g(n)會在f(n)之下
所以這個操作的asymptotic notation是 Ω(n)


----------------------------------------------------------------------------------------------------------
延伸閱讀

※各符號的詳細定義：
└ Big Oh：f(n) = Ο(g(n)) iff ∃正的常數c和n0，使得f(n) ≤ c × g(n), ∀ n >= n0
└ Theta：f(n) = Θ(g(n)) iff ∃正的常數c1,c2和n0，使得c1 × g(n) ≤ f(n) ≤ c2 × g(n) , ∀ n ≥ n0
└ Omega：f(n) = Ω(g(n)) iff ∃正的常數c和n0，使得f(n) ≥ c × g(n), ∀ n >= n0

註：專用術語/縮寫
iff ：if and only if (若且唯若，只有在後面的狀況下成立前面才會成立，反之亦然)

參考資料：
http://notepad.yehyeh.net/Content/DS/CH01/3.php