[ML] Big-O : The complexity of algorithm

日期: 2020-Jan-19, 作者: Tim Wong

為 algorithm 算一算它的 complexity，我們就有了比較各種 algorithm 是好是壞的基礎。

以下在algorithm 的動作的算它一個operation:

- assign value: e.g. x = 10
- array 中找個數: e.g. thisArray[10]
- 比較兩個variables: e.g. a > b
- 四式運算: b+1

那就算一算下面的 algorithm 有多少operation 吧!

var M = A[0]  
for (var i=0; i <n; i++){
 if (A[i] >= M){
  M = A[i]
 }
}
#-------------------------
1.A[0] ... 算一個
2.M=A[0] ... 算一個
3.i=0 ... 算一個
4.i<n ... 算一個

5.A[i] ... 算一個
6.A[i] >= M ... 算一個
7.A[i] ... 又算一個
8.M = A[i] ... 算一個
9.i++ ... 算一個
10.i<n ... 算一個
然後，又重覆5,6,7,8,9,10, 重覆n次. 

所以上面algorithm 的complexity 是 Θ(4+6n)。

因為我們都只關心當n 很大的時候algorithm 的運作時間，那些無關痛癢的就不管了，所以 Θ(4+6n) 就變成 Θ(n) 。對的，那個 「4」在 n 很大時當然不足掛齒，而那個「6」是因為每種不同programming langage 及不同的CPU 都會對看來一樣的operation 有著不同的處理方法，為了方便比較，所以連這個「6」都不要了。

因此：

f(n) = n² +9999n + 9999 → f(n) = n²

f(n) = n⁶ + 100n⁵ → f(n) = n⁶

f(n) = 99999 → f(n) = 1 所以，只要algorithm 中沒有looping 的都是 complexity = 1.

Big-O notation

上面說的是actual complexity，但可以想到這麼數很麻煩，而且還有很多不同特例，不一定能算的盡。故，表達algorithm 的最大complexity 就是了。例如一個f(n) = n² 的algorithm 有可能在特例時只有f(n) = n³。我例就用

f(n) = n² → O(n²) , o(n³) ： Big-O complexity n² or Small-O complexity n³.

就這麼簡單。

全力衝刺中的一團火

我是阿Tim | timwong.ai@gmail.com