# Day 32 : Big O 分類
先對常用常用函式類型做Big O的整理，再一一做說明
| Name | Notation |
|:----------------------:|:-----------:|
| Constant | $O(1)$ |
| Logarithmic | $O(log(n))$ |
| Linear | $O(n)$ |
| Quadratic | $O(n^2)$ |
| Polynomial | $O(n^c)$ |
| Exponential | $O(c^n)$ |
| Factorial or N-power-N | $O(n!)$ |

增長速度圖形如下
(圖一、資料來源:[Big O Cheat Sheet – Time Complexity Chart](https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/))

## Constant function
有一個固定常數的函式，如 $f(n)=100$，其得到的複雜度不會隨著input size的大小而做改變，這時候Big O為 $O(1)$。

常用的操作:
* 對一個stack進行push或式pop的動作
* 透過key存取hash table裡面的元素

## Logarithmic
當這個複雜度的結果與輸入的對數呈現正比的關係時，此時Big O為 $O(log(n))$。下圖為$f(n)=log_2(n)$之圖形。
(圖二，自行繪製)

常用的操作:
* Binary search : 每次查找都可以刪除一半的輸入，不需要進行遍歷，因此當input size增加時，複雜度的增長速度會減慢。

## Linear
當這個複雜度的結果與輸入呈現正比的關係，代表演算法的Big O為線性，例如 $f(n)=n$，此時Big O為 $O(n)$。

常用的操作:
* 在array中找一個元素
* 在liked list中遍歷找最大值或最小值

## Quadratic (Polynomial的一種)
當這個複雜度的結果與輸入的平方呈現正比的關係時，此時Big O為 $O(n^2)$，如 $f(n)=n^2$。
此時當input size增加的時候，複雜度也就是執行的時間會增加很快，比較常見的例子就是當我們要使用nested loop的時候。

for i := 0; i < n; i++{
    
    ...

  for j := 0; j < n; j++{

      ...
      
  }
}

## Exponential
當這個複雜度的結果與輸入呈現指數得成長關係時，此時Big O為 $O(log(c_n))$，如 $f(n)=2^n$。
當input size增加時，此函式的複雜度會呈指數級成長，成長速度非常快，最常用的應用地方為 **power set**。

## Factorial
當這個複雜度的結果與輸入的階乘呈現正比關係時，此時Big O為 $O(n!)$，為非常低效的演算法，所以也較少使用。

## References
1. [那些聽起來很專業的「演算法 Algorithm」跟「Big O notation」到底是什麼？](https://www.educative.io/courses/data-structures-and-algorithms-go/B8E4zYBZNON)
2. [Big O Cheat Sheet – Time Complexity Chart](https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/)
3. [Data Structures & Algorithms In Go](https://www.educative.io/courses/data-structures-and-algorithms-go)
4. [Time and Space complexity with Golang](https://medium.com/@jeelrupapara/day-1-data-structure-and-algorithms-time-and-space-complexity-with-golang-a380d5914cc9#:~:text=O(2%5En))

###### tags: `Algorithm`
###### tags: `Big O`