# [資演] 1- 時間複雜度與空間複雜度
###### tags: `資演`

在進入到正題之前，我們先考察一下演算法的定義（出自[維基百科](https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95)）：
> 在數學和電腦科學之中，演算法（algorithm）指一個被定義好的、計算機可施行其指示的**有限步驟或次序**，常用於計算、數據處理和自動推理。演算法是**有效**方法，包含一系列**定義清晰的指令**，並可於**有限的時間及空間**內清楚的表述出來。

在這邊我們特別注意幾個關鍵字：有限的步驟和次序、有效、定義清晰的指令，以及有限的時間及空間。

我們要怎麼衡量一個演算法的好壞呢？要衡量一個演算法的好壞，最基本的兩個指標是這個演算法需要多少計算**時間**，以及他需要用到的儲存**空間**有多少，也就是**時間複雜度**和**空間複雜度**。
那麼，這些複雜度我們要怎麼量測呢？例如在leetcode上提交一個程式碼，並成功編譯後，會顯示出你的程式碼的執行時間和使用的記憶體：


但是，比較常見的情況是，我們希望在執行程式碼之前就先評估演算法的複雜度，再決定要不要採用這個演算法。另外，在不同的機器上執行相同的程式，執行速度也會有差異。因此，我們需要有一個共同的標準來評估演算法的效能。這種時候，就必須使用一些**複雜度分析**的技巧了。

## 時間複雜度
一個演算法所需要的時間，我們通常會用這個演算法所需要的**步驟數**來衡量。這個步驟數要怎麼計算呢？

舉例來說，我們現在要尋訪一個長度為 $n$ 的list，這個list的名稱為`my_list`：

for i in range(n):
    print(my_list[n])

每次`print`都算是一個步驟的話，這段code需要花費幾個步驟才能完成呢？這很容易看出來，因為`my_list`一共有 $n$ 個element，所以總共需要花費 $n$ 步才能完成尋訪。

再舉一個例子，現在我們有一個長度為 $n$、已經由小到大排列好的list，我們叫它`sorted_list`。我們想使用binary search在裡面檢查一個元素是否存在，**最多**需要花費幾個步驟？

我們先複習一下binary search。以下是binary search的pseudocode：

left = 左邊的邊界
right = 右邊的邊界
while (左比右小，代表邊界還正常) {
    mid = 左右邊界的中間點
    if (數列中間點的數值大於 target) {
      右半邊可以不用看了，因此把右邊邊界移到中間
    } else if (數列中間點的數值小於 target) {
      左半邊可以不用看了，因此把左邊邊界移到中間
    } else {
      找到答案了！
    }
}

:::spoiler 用Python寫出來是這個樣子的
def binary_search(sorted_list, target):
#設置選取範圍的指標
left = 0
right = len(sorted_list) - 1
while left <= right:
mid = (left + right) / 2 #取中間索引的值
if sorted_list[mid] < target: #若搜尋值比中間的值大，將中間索引+1，取右半
left = mid + 1
elif sorted_list[mid] > target: #若搜尋值比中間的值小，將中間索引+1，取左半
right = mid - 1
else: #若搜尋值等於中間的值，則回傳
return mid
return -1

:::

在binary search中，需要花最多時間的狀況，是要查找的element不存在的情況。這種時候需要花費多少步驟呢？假設`sorted_list`的長度 $n = 8$，並且要查找的element=比所有`sorted_list`裡面的element還要大：
* 第一次查找
`left = 0`
`right = 7`
`mid = 3`
--> `target > mid`
--> 選擇右半邊
* 第二次查找
`left = 4`
`right = 7`
`mid = 5`
--> `target > mid`
--> 選擇右半邊
* 第三次查找
`left = 5`
`right = 7`
`mid = 6`
--> `target > mid`
--> 選擇右半邊
--> `target > sorted_list[7]`
--> **找不到**

我們可以發現，如果`sorted_list`的長度是8，尋找一個element所需要花費的最大步驟就是3次：
$$
2^3 = 8
$$或者是
$$
\log _2 8 = 3
$$也就是說，binary search的複雜度是$\log n$。

## Big-O notation
剛才我們粗略介紹了一下時間複雜度的概念，現在我們要來正式定義它。

複雜度分析的notation有三種：
* $Ο$ (Big-O)
演算法時間函式的上限（upper bound）。
* $\Omega$ (Omega)
演算法時間函式的下限（lower bound）。
* $\Theta$ (Theta)
演算法時間函式的上限與下限，也就是 $O =\Omega=\Theta$ 的時候。

舉例來說，前面提到的尋訪演算法，最多需要$n$步，所以它的複雜度為 $O(n)$。另一方面，binary search的複雜度是$O(\log(n))$。你可能會想問，如果要找的element剛好在第一次查找的`mid`的位置，那就只需要一步，也就是說，binary search是一個$\Omega(1)$的演算法？然而這樣說是不對的！參考[這篇文章](https://stackoverflow.com/questions/9459507/complexity-of-binary-search)，正確的說法應該是：
* 對於最佳狀況，你最少需要$\Omega(1)$次查找，最多也只需要$O(1)$次查找，所以binary search的最佳狀況複雜度是$\Theta(1)$
* 對於最差狀況，你最少需要$\Omega(\log n)$次查找，最多也只需要$O(\log n)$次查找，所以binary search的最差狀況複雜度是$\Theta(\log n)$

也就是說，最佳狀況和最差狀況必須**分開檢視**，不能混為一談！

## 複雜度的計算
事實上剛才介紹的這組 big-O notation都是屬於一種漸進符號（asymptotic notation），嚴謹一點的定義可以參考[這篇文章](http://alrightchiu.github.io/SecondRound/complexityasymptotic-notationjian-jin-fu-hao.html)，在這邊我們只介紹粗略的計算方式。

首先，在計算big-O時，我們只看增長最快的那項，並且忽略一切常數factor。例如 $3x^3 + 4x^2 + 2x + 4$，我們可以說它等於$O(x^3)$。至於增長速度怎麼看呢？很明顯的，對於多項式，項次越大增長速度越快，複雜度也就越高。增長最快的是$O(a^n)$，其中$a$是常數，也就是所謂的指數增長。接著是多項式$O(n^k)$，其中$k>1$。再來是線性$O(n)$。$O(\log n)$ 增長速度又比線性再更慢。可以把big-O notation想成是一種分等級的方式，指數增長是一種複雜度等級，再來多項式又是一種複雜度等級...等。


Big-O notation 有幾個重要的數學性質：

* 加法
若 $f_1(n)$ 為 $O(g(n))$ 且 $f_2(n)$ 為 $O(g(n))$，則 $f_1(n) + f_2(n)$ 也是 $O(g(n))$。
意思是說，兩個屬於相同複雜度等級的函數相加，也會是那個相同的複雜度等級。
* 常數factor
若 $f_1(n)$ 為 $O(g(n))$，則對於任意常數$k$乘以 $f_1(n)$ 也是 $O(g(n))$。
意思是說，乘以常數不會改變一個函數的複雜度等級。
* 乘法
若 $d(n)$ 為 $O(f(n))$，而 $e(n)$ 為 $O(g(n))$，則$d(n)\cdot e(n)$ 為 $O(f(n) \cdot g(n))$。
意思是說，兩個函數相乘的複雜度，相當於其個別複雜度的相乘。

更多 big-O notation 的數學性質可以參考[這份講義](https://www.cs.mcgill.ca/~blanchem/250/2017/Lecture12_handouts.pdf)。

## 空間複雜度
空間複雜度和時間複雜度的計算方式相同。通常空間複雜度和時間複雜度是可以trade off的，也就是說，我們可以用高一點的空間複雜度來換取低一點的時間複雜度，反之亦然。在記憶空間相對便宜的現代，我們更傾向於用以空間換取時間。一個很好的例子是排序演算法。排序演算法有很多種，每種各有其優缺，這就是因為不同的演算法做了不一樣的trade off。