---
# System prepended metadata

title: 什麼是演算法？
tags: [演算法, 資料結構, leetcode觀念]

---

# 什麼是演算法？
演算法(Algorithm)是透過一系列的步驟、規則或計算，來解決特定問題或完成某項任務所需的資訊。常見的演算法用途，如：排序、搜尋、最佳路徑、加/解密、機器學習、影像處理等。

$$ 
輸入(Input) + 演算法(Algorithm) = 輸出(Output)
$$ 

如果以日常生活舉例，餐廳廚師將<u>多種食材</u>依照<u>食譜</u>的洗、切、調味/醃製、煮/蒸/煎/炸等一系列的操作，烹調出<u>一道美味的佳餚</u>。而<u>食譜</u>就可視為<u>美味佳餚的演算法</u>

$$ 
食材 + 食譜 = 美味佳餚
$$ 

透過以上，我們可以簡單歸納出演算法的特徵包括
1. 明確性：需明確清晰的定義步驟，無歧義
2. 有限性：需在有限的步驟內完成任務或解決指定問題
3. 輸入及輸出：需有零個或一個以上的輸入，以及需有至少一個輸出
</br>

# 演算法的評估
當我們依據特定問題，定義出解決的演算法時，我們要如何評估該演算法的好壞？

演算法的執行或計算過程，不外乎皆需要時間與記憶體(空間)，來支持演算法的執行過程。

所以，我們可以依據執行該演算法，所需耗費的時間長短，以及所佔用的記憶體(空間)大小，來評估演算法的好壞。
</br>

# 複雜度（Complexity）
所需耗費的時間長短，我們可以使用「時間複雜度(Time Complexity)」來表示。

而所佔用的記憶體(空間)大小，我們可以使用「空間複雜度(Space Complexity)」來表示。

其中需注意的是，<u>時間複雜度所評估的時間，是指執行步驟的次數，而非指執行所需的時間。</u>

因為執行所需的時間，不僅與演算法的定義相關，還與執行背景有所關聯。
</br>

以程式的角度來看，相同的輸入資料及演算法，若是用不同的程式語言撰寫，或是用不同規格的桌電/筆電/VM執行，演算法所需的時間也就不會一致。

若以日常生活舉例，相同的麵團，使用家用的烤箱以及使用餐廳的專業烤箱，兩種不同功率的烤箱，執行烘烤所需的時間也不會一致。

因此，在時間複雜度中，所紀錄的時間是指執行步驟的次數，而非指實際的執行時間。
</br>

一般而言，演算法會隨著輸入項(n)的不同，而有對應的時間或空間改變，比如 :
```=
int n = 10, sum = 0;
for(int i=0;i<n;i++){
    sum++;
}
```
以時間角度來說，迴圈的次數會隨著n而改變，輸入項(n)與時間成正比關係。

若以f(n)表示，這段程式執行所需的時間可記為 
$$
f(n) = n
$$

用圖表畫出則會<u>呈現線性</u>的樣子
![f(n) = n](https://hackmd.io/_uploads/BJQAahT-yg.png)
</br>

假設再將程式調整為雙層迴圈
```=
int n = 10, sum = 0;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        sum++;
    }
}
```

迴圈則會執行 `n^2` 次，可記為 
$$
f(n) = n^2
$$

![f(n) = n^2](https://hackmd.io/_uploads/S1ixb6p-Jg.png)

綜上所述，我們可以簡單從輸入項(n)的改變，歸納出執行次數 f(n) 的變化。
</br>

## 多項式
當然，一般能夠解決問題的演算法，也不會單純的只有一個迴圈，通常會由多個步驟的程式碼所組成。

假設我們將前述兩段程式碼，視為同一個演算法的「步驟一」及「步驟二」，其演算法的總執行次數可記為 
$$
    f(n) = n^2 + n
$$

當其複雜度為多項式，且所輸入的輸入項(n)越大時，最高次方項的值，佔該函數總值的比例也就越大。

以 $f(n) = n^2 + n$ 的多項式來看，假設 n = 10,000

```
f(n) = (10,000 * 10,000) + 10,000 
     = 100,000,000 (99.99%) + 10,000 (0.01%)
     = 100,010,000 (100%)
```
</br>

我們可以觀察出「最高次方項的值，是影響函數總值的最大因素」，至於多項式的其他項目則可忽略不計。
</br>

# 漸進符號（Asymptotic Notation）
實務上一般會使用大Ｏ符號來表達其複雜度的漸進式。

然而，漸進式的表達方法不僅有大Ｏ符號，還有其他如：大Ω符號、大θ符號等。

* 大Ｏ符號，Big-O(O)
    表示演算法的上限/上界(Upper Bound)，即「最壞的執行狀況」
    
* 大Ω符號，Big-Omega(Ω)
    表示演算法的下限/下界(Lower Bound)，即「最好的執行狀況」

* 大θ符號，Big-Theta(θ)
    表示演算法的上、下限/界，其描述「含蓋所有的執行狀況」

而演算法中，通常大家比較關注的點是<u>最少</u>需要耗費多久的時間，以及<u>最少</u>需要多少的記憶體，才能夠成功執行完成所有的情境，所以我們可以簡單用演算法的上限/上界(Upper Bound)來看，即「最壞的執行狀況」。

也因此，<u>演算法的時、空間複雜度的表達，通常使用大Ｏ符號表示居多</u>。

每種漸進符號皆有對應的數學式，詳細可再參考其他文獻。
</br>

# 如何判斷複雜度？
那麼我們平常開發程式時，可以如何判斷所撰寫的程式碼，是屬於哪一種「時間複雜度」以及哪一種「空間複雜度」？

針對這兩大部分，因為需要說明的地方較多，另拆成兩篇文章來進行說明。

其中內容也涵蓋一些常見開發情境的時、空間複雜度判斷。

[時間複雜度](https://hackmd.io/@Lion-Le/rkrvv1qMke)

[空間複雜度](https://hackmd.io/@Lion-Le/ByTtSQ771g)
</br>

# 重點歸納
簡單為這一系列的演算法文章做個重點整理

* 演算法的定義
演算法是指透過一系列的步驟、規則或計算，來解決特定問題或完成某項任務所需的資訊

* 演算法的特性
    1. 明確性：需明確清晰的定義步驟，無歧義
    2. 有限性：需在有限的步驟內完成任務或解決指定問題
    3. 輸入及輸出：需有零個或一個以上的輸入，以及需有至少一個輸出

* 演算法的評估
演算法的好壞可透過「時間複雜度」以及「空間複雜度」兩點來綜合評估，
兩者分別代表「執行所需耗費的時間」以及「執行所需耗費的空間(記憶體)」

* 複雜度的表示法
可使用「漸進符號」表示其複雜度的漸進方式

* 漸進符號的種類
可依據所需評估的面向，如：最佳情境、最壞情境、平均情境等
使用其對應的「漸進符號」，以下為幾種常見的漸進符號
  1. 大Ｏ符號，Big-O(O)
    表示演算法的上限/上界(Upper Bound)，即「最壞的執行狀況」。是評估複雜度中最常用的「漸進符號」
  2. 大Ω符號，Big-Omega(Ω)
    表示演算法的下限/下界(Lower Bound)，即「最好的執行狀況」
  3. 大θ符號，Big-Theta(θ)
    表示演算法的上、下限/界，其描述「含蓋所有的執行狀況」

* 常見的演算法
  二元搜尋法(Binary Search)、遞迴(Recursion)、深度優先搜尋(Depth-First Search，DFS)、廣度優先搜尋(Breadth-First Search，BFS)、動態規劃(Dynamic Programming，DP）以及各種排序法，如：氣泡排序、選擇排序、合併排序等

</br>

# 總結
對於百萬、千萬資料量級以上的系統，或是資源較為有限的嵌入式設備、IOT主機板等使用情境，會需要特別注意「時間複雜度」與「空間複雜度」

對於其他中、小型系統而言，時間複雜度不要達到指數級`O(2^n)`以上，空間複雜度不要達到平方級`O(n²)`以上，大多時候皆為可容忍程度

資料量級越大的系統，在執行不同複雜度的程式時，感受上也會相對的顯著

至此，演算法系列的文章大概告個段落，這系列的文章，僅簡單提及與說明演算法的各個觀念。

若對其觀念有興趣或想再更深入研究者，可再參考其他演算法的文獻、書籍或資源等。
</br>

>[!Tip] 
文章內容皆為個人整理的觀點，以及整理後的個人想法，如內容有錯誤或疑慮的部分，歡迎提出討論，收到後會盡快修正！
