- Asymptotic analysis 漸進分析
- 保持持續討論的態度,asymptotic analysis 是討論不同解法彼此之間的 trade off,所以其實沒有一個完全正確的解法,重點在於不同解法之間的優劣。
來看個例子
int example(int n) {
for(int i=0; i<10; i++) {
//do O(1) work
}
}
在這個例子中,不管 n 如何改變 ...n=1000
、n=100000000
,結果都會保持 constant,所以他的曲線或者 paramater 就會像是 O(1)
接下來來看一些 O(n) 的例子
int example(int n) {
for(int i=0; i<n; i++) {
//do O(1) work
}
}
int example(int n) {
for(int i=0; i<2n; i++) {
//do O(1) work
}
}
上面兩個例子,可以清楚的看出來當 n 變大時,會影響運行的次數,呈現 linear 的 parameter,而且第二個例子的斜率更大,但我們其實比較看重不同 parameter 的變化模式,所以可以都簡略為 O(n)。
Asymptotic Bounding 101
如何判斷好壞
- 通常要判斷一個演算法,我們可能會分為 best 、 average、worst
- 下面會可以用一些指標來表達多好、多壞、範圍等
O() -> bigO //Upper bound,越高,演算法越沒效率
o() -> little o
Θ( ) -> theta //exact bound
Ω( ) -> big omega //越高,演算法越有效率
ω( ) -> little omega
更深入的談 asymptotic bounding
來看一段關於 asymptotic 的數學演示,展示如何逼近 upper bound
T(n)
is O(f(n)) "if"
T(n) <= C*O(f(n))
for all n>= n
接下來我們假若把 T(n) 的曲線畫出來,然後試試用 O(n)、O(n2)、log(n) 來逼近,會發現只有 linear 的 O(n) 可以無窮逼近 T(n),所以這時候我們就不會在意 C (constant) 是如何變化,因為只有在選對 "模式" 的狀態下,才能逼近正確的 T(n)