# 時間複雜度與空間複雜度 Time Complexity & Space Complexity

- Time Complexity：電腦執行演算法所需要耗費的時間成本
- Space Complexity：電腦執行演算法所需要耗費的空間 ( 記憶體 ) 成本

一般來說​「時間複雜度」與「空間複雜度」之間是可以相互 trade off 的！
> 而相互 trade off 的意思是：
在某些情況底下，我們是可以讓程式多用一些記憶體空間來多記一些資訊，就可以省去一些重複的運算來加速程式的執行時間；或者我們完全沒有多餘的記憶體資源可以使用，也可以透過把一些原本可以靠記憶體存儲的資訊改用重複計算的方式來取得。

# Time Complexity
電腦執行的速度相當快，而且不同電腦的規格也不同是難以比較的。所以主要的概念會是「演算法執行需要幾個指令」來計算。

這邊以 Jason Chen 大大的範例來表示

```C
void example(int n) {
    int i, j, sum;                  // 只是在記憶體上宣告變數，不需執行。
    sum = 0;                        // 將數值 0 assign 給變數 sum，執行 1 次。
    for (i = 0; i < n; i++) {       // 從 i=0 累加到 i=n 判斷條件不成立時結束，共執行 n+1 次。  
        for (j = 0; j < n; j++) {   // 從 j=0 累加到 j=n 判斷條件不成立時結束，共執行 n*(n+1)次。
            sum = sum + i * j;      // 共執行 for i 的 n 次 * for j 的 n 次 = n^2 次。
        }
    }
    for (i = 0; i < n; i++) {       // 從 i=0 累加到 i=n 判斷條件不成立時結束，共執行 n+1 次。
        sum -= i;                   // 在 for i 內執行 n 次。
    }
}
```

在上面的範例裡面名為 example 這個 function，總共需要執行：  
`1  +  (n+1)  +  n*(n+1)  +  n*n  +  (n+1)  +  n  =  2(n*n) + 4n + 3` 個指令

而在標示複雜度的時候，只需要取最高次方項，並且可忽略項次前的係數。所以最後上述的 `2(n*n) + 4n + 3` 會變為 `O(n^2)`。`2(n*n)` => `n^2`，`4n+3` 忽略。

# Space Complexity

```python
def create_array(n):
    arr = list()
    for i in range(n):
        arr[i] = i
```

上面的範例其複雜度是 `O(n)`，因為可以看到使用 `arr` 來儲存 `i` 的值。而其長度受制於 `n` 的大小。


# 總結

從下圖可以看到不同常見的複雜度之前在 `n` 越來越大後的差異
當 `n` 無限大時，其所需的成本排序：`1 < log n < n < n log n < n^2 < n^3 < 2^n < n!`

![Complexity Chart](https://i.imgur.com/Os1XsrJ.png)


# Reference

- https://jason-chen-1992.weebly.com/home/time-space-complexity