---
# System prepended metadata

title: 演算法筆記
tags: [演算法]

---

# 演算法筆記

**把我開發專案時常用(也有不常用但覺得很屌的)的演算法記錄下來，雖然都很基礎但很好用（但還是函式庫香**

## 1. 排序 (Sorting)

### (1) 氣泡排序 (Bubble Sort)
**重複掃描序列**，依序比較相鄰的兩個元素，  
若前一個比後一個大，就交換它們的位置。  
重複多次，得的到遞增（或遞減）順序。  

---

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(n)$（當資料已排序） |
| 平均情況 | $O(n²)$ |
| 最差情況 | $O(n²)$ |

#### ● 空間複雜度
$θ(1)$（原地排序，不需額外空間）

---

#### ● 範例 (cpp)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `array` | 要進行排序的目標陣列 | `int[]` |
| `array_len` | 陣列的長度（元素個數） | `int` |

```cpp=
for (int i=0; i< array_len-1; i++) {
    // 到 array_len-1 就可以，最後一項會自動歸位
    for (int j=0; j< array_len-i-1; j++) {
        // 比大小，前項較大的話就交換
        if (array[j]>array[j+1]) {
            int temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
        }
    }
}
```

### (2) 合併排序法 (Merge sort)
**合併排序**是一種**分治法 (Divide and Conquer)** 的排序演算法。  
它將陣列不斷分割成更小的部分，直到只剩一個元素，再將這些子陣列依序合併回來，在合併過程中完成排序。  

**步驟**
1. 將原始陣列分為左右兩半
2. 遞迴地對左右子陣列進行合併排序
3. 將兩個排序好的子陣列合併成一個完整的有序陣列

---

#### ● 時間複雜度
$O(n \log n)$（最佳、平均、最差皆相同）
#### ● 空間複雜度
$O(n)$（需額外空間分離原始陣列）
#### ● 範例 (cpp)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `array` | 要進行排序的目標陣列 | `int[]` |
| `l` | 陣列左界（起始索引） | `int` |
| `m` | 陣列分界點（中間索引） | `int` |
| `r` | 陣列右界（結束索引） | `int` |

```cpp=
// 合併兩個已排序的子陣列
// 左半 [l, m]，右半 [m+1, r]
void merge(int array[], int l, int m, int r) {
    int n1 = m - l + 1;  // 左半長度
    int n2 = r - m;      // 右半長度

    // 暫存左右子陣列
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = array[l + i];
    for (int j = 0; j < n2; j++) R[j] = array[m + 1 + j];

    // 合併過程
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) array[k++] = L[i++];
        else array[k++] = R[j++];
    }

    // 將剩餘元素複製回主陣列
    while (i < n1) array[k++] = L[i++];
    while (j < n2) array[k++] = R[j++];
}

// 主函數：遞迴分割 + 合併
void merge_sort(int array[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;  // 中點

        merge_sort(array, l, m);      // 排左半
        merge_sort(array, m + 1, r);  // 排右半
        merge(array, l, m, r);        // 合併
    }
}
```

### (3) 快速排序法 (Quick Sort)

它透過選擇一個基準值 (pivot)，將陣列分為「比 pivot 小」與「比 pivot 大」的兩部分，  
然後遞迴地對兩側進行相同的操作，直到整個陣列完成排序。

---

#### ● 演算法步驟
1. 選擇一個元素作為 **pivot**（通常取中間或最後一個）
2. 將陣列中小於 pivot 的元素放左邊，大於 pivot 的放右邊
3. 對左右子陣列重複步驟 1–2（遞迴）

---

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(n \log n)$ |
| 平均情況 | $O(n \log n)$ |
| 最差情況 | $O(n^2)$（當資料幾乎有序時） |

#### ● 空間複雜度
-  $θ( \log n)$ (遞迴呼叫堆疊深度)

---

#### ● 範例 (C++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `array` | 要進行排序的目標陣列 | `int[]` |
| `low` | 區間起始索引 | `int` |
| `high` | 區間結束索引 | `int` |

```cpp=
// 分區函式：將陣列分成比 pivot 小與比 pivot 大的兩部分
int partition(int array[], int low, int high) {
    int pivot = array[high];  // 選擇最右邊元素為 pivot
    int i = low - 1;          // i 為小於 pivot 區間的最後索引

    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(array[i], array[j]);  // 將小於 pivot 的元素移到左邊
        }
    }
    swap(array[i + 1], array[high]);  // 把 pivot 放到正確位置
    return i + 1;                     // 回傳 pivot 的最終位置
}

// 主函式：遞迴進行快速排序
void quick_sort(int array[], int low, int high) {
    if (low < high) {
        int pi = partition(array, low, high);

        quick_sort(array, low, pi - 1);  // 排左半
        quick_sort(array, pi + 1, high); // 排右半
    }
}
```

### (4) 插入排序法 (Insertion sort)
從第二項開始一直比自身前幾項，並在自身的值小於此序列的值時將此項插入其序列，否則不動，並繼續比下去。

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(n)$ （當資料幾乎有序時）|
| 平均情況 | $O(n^2)$ |
| 最差情況 | $O(n^2)$（當資料為倒過來的有序時 (國語不好(´･ω･`) |

#### ● 空間複雜度
-  $θ(1)$ （原地排序，不需額外空間）

#### ● 範例 (C++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `array` | 要進行排序的目標陣列 | `int[]` |
| `array_len` | 目標陣列的長度 | `int` |

```cpp=
void insertion_sort() {
    for (int i = 1; i < array_len; i++) {          // 從第二個元素開始
        int key = array[i];                        // 要插入的值
        int j = i - 1;

        // 向左找適合的位置
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];               // 向右移動
            j--;
        }

        array[j + 1] = key;                        // 插入 key 到正確位置
    }
}
```

## 2. 搜索 (Searching)
### (1) 線性搜索
直接遍歷所有資料 
Very Easy

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(1)$ （目標資料在第一個時）|
| 最差情況 | $O(n)$（目標資料在最後一個時）|

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `t_value` | 目標數值 | `int` |
| `t_index` | 目標數值在目標陣列內的 index | `int` |
| `array` | 要進行排序的目標陣列 | `int[]` |
| `array_len` | 目標陣列的長度 | `int` |

```cpp=
int t_index = -1;
for (int i=0; i<array_len; i++) {
    if (array[i] == t_value) {
        t_index = i;
        break;
    } 
}
if (t_index != -1) printf("目標值 t_value 位於 array 內的 index: %d", t_index);
else printf("在 array 內未找到目標值 t_value");
```

### (2) 二分搜 (Binary Search)
>此演算法只能在**已排序**的陣列上使用!

取中間 index比較index值數字的大小，若較小往小的地方跑，較大的話往大的地方跑
繼續下去直到找到目標index 

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(1)$ （陣列中間的數值剛好是被搜索的數值）|
| 最差情況 | $O(\log n)$（嚴格來說是 $log_2 (n)$）|

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `t_value` | 目標數值 | `int` |
| `t_index` | 目標數值在目標陣列內的 index | `int` |
| `array` | 要進行排序的目標陣列 | `int[]` |
| `array_len` | 目標陣列的長度 | `int` |

```cpp=
int t_index = -1;
int right = arr_len-1;
int left = 0;

while (right >= left) {
    // 中間 index
    int middle = (right + left) / 2;
    // 大於目標值，往右跑
    if (array[middle] > t_value) left = middle - 1;
    // 小於目標值，往左跑
    else if (array[middle] < t_value) right = middle + 1;
    // 等於目標值，輸出
    else {
        t_index = middle;
        break;
    }
}

if (t_index != -1) printf("目標值 t_value 位於 array 內的 index: %d", t_index);
else printf("在 array 內未找到目標值 t_value");
```

### (3) 插補搜尋 (Interpolation Search)
>此演算法只能在**已排序**的陣列上使用!

二分法的變體，根據目標值與區間比例預估位置，比二分搜尋更適合均勻分布的數列。

#### ● 時間複雜度
| 情況 | 複雜度 |
|:--|:--|
| 最佳情況 | $O(1)$ 目標剛好被第一次預估命中|
| 最差情況 | O($log(log (n))$) (資料均勻分布) ~ $O(n)$ (資料沒有均勻分布)|

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `t_value` | 目標數值 | `int` |
| `t_index` | 目標數值在目標陣列內的 index | `int` |
| `array` | 要進行排序的目標陣列 | `int[]` |
| `array_len` | 目標陣列的長度 | `int` |

```cpp=
int t_index = -1;
int right = array_len - 1;
int left = 0;

while (t_value >= array[left] && t_value <= array[right] && right >= left) {
    int p_index;
    // 插補預測 index
    p_index = left + (t_value - array[left]) / ( array[right] - array[left]) * (right - left);
    // 左右相遇，看最後一個 index 是不是目標值 
    if(left == right){
        if(t_value == array[left]) return left;
        else break;
    }
    // index 是目標值 
    if(t_value == array[p_index]) {
        t_index = p_index;
        break;
    }
    // 大於目標值，往右跑
    else if(t_value > array[p_index]) left=p_index+1;
    // 小於目標值，往左跑
    else right = p_index-1;
}

if (t_index != -1) printf("目標值 %d 位於 array 內的 index: %d\n", t_value, t_index);
else printf("在 array 內未找到目標值 %d\n", t_value);
```

## 3. 圖論演算法 (Graph Algorithms)
 >這裡都以"找最近的路線"為範例
 >老實說我很少用到（只有解題時用到
### (1) 廣度優先搜索 BFS
由起點開始，**一層一層地擴散**，直到找到終點為止。
BFS 在無權重的地圖中能找到**最短路徑**。

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `map` | n×m 地圖 (0 為道路; 1 為障礙) | `int[][]` |
| `n`, `m` | 地圖行列大小 | `int` |
| `start` | 起點座標 (x, y) | `pair<int, int>` |
| `goal` | 終點座標 (x, y) | `pair<int, int>` |

```cpp=
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Point {
    int x, y;
};

int main() {
    int n = 5, m = 6;
    // 我們的地圖
    vector<vector<int>> map = {
        {0, 0, 0, 0, 1, 0},
        {1, 1, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 1},
        {0, 1, 1, 1, 0, 0},
        {0, 0, 0, 1, 0, 0}
    };

    Point start = {0, 0};
    Point goal  = {4, 5};

    // 動作 (如向上 (dx[3], dy[3])
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    // 紀錄走過的地方
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    // 紀錄步數
    vector<vector<int>> dist(n, vector<int>(m, -1));
    
    // 要處裡的點位陣列
    queue<Point> q;
    // 把起點加進去
    q.push(start);
    visited[start.x][start.y] = true;
    dist[start.x][start.y] = 0;

    bool found = false;

    while (!q.empty()) {
        // 將要處理的點位
        Point cur = q.front(); 
        q.pop();
        
        // 檢查到終點了沒
        if (cur.x == goal.x && cur.y == goal.y) {
            found = true;
            break;
        }
        
        // 處理上下左右 4 個點
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            // 有沒有出界?
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            // 有沒有走過?
            if (map[nx][ny] == 1 || visited[nx][ny]) continue;
            
            // 標記
            visited[nx][ny] = true;
            // 紀錄步數
            dist[nx][ny] = dist[cur.x][cur.y] + 1;
            // 新增點位
            q.push({nx, ny});
        }
    }

    if (found) cout << "找到路線！最短距離為 " << dist[goal.x][goal.y] << " 步\n";
    else cout << "無法到達終點\n";

    return 0;
}
```

### (2) 深度優先搜索 DFS
依照指定的搜索順序，嘗試所有可能的路線，直到找到目標為止。
相比 BFS，DFS 會**一條路走到底**，適合用來找是否能到達某個位置或**所有可能的路徑**。

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `map` | n×m 地圖 (0 為道路; 1 為障礙) | `int[][]` |
| `n`, `m` | 地圖行列大小 | `int` |
| `start` | 起點座標 (x, y) | `int[]` |
| `goal` | 終點座標 (x, y) | `int[]` |
```cpp=
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 我們的地圖
int n = 5, m = 6;
vector<vector<int>> map = {
    {0, 0, 0, 0, 1, 0},
    {1, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 1},
    {0, 1, 1, 1, 0, 0},
    {0, 0, 0, 1, 0, 0}
};

// 動作 (如向上 (dx[3], dy[3])
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 起點與終點
int start[2] = {0, 0};
int goal[2]  = {4, 5};

// 紀錄走過的地方
vector<vector<bool>> visited(n, vector<bool>(m, false));
bool found = false;

void dfs(int x, int y) {
    // 超出邊界或遇障礙物
    if (x < 0 || y < 0 || x >= n || y >= m) return;
    if (map[x][y] == 1 || visited[x][y]) return;

    // 到達目標
    if (x == goal[0] && y == goal[1]) {
        found = true;
        return;
    }

    visited[x][y] = true;

    // 遞迴探索四個方向
    for (int i = 0; i < 4; i++) {
        dfs(x + dx[i], y + dy[i]);
        // 若已找到就提前結束
        if (found) return; 
    }

    // 回溯（若要找所有路徑才需要）
    visited[x][y] = false;
}

int main() {
    dfs(start[0], start[1]);

    if (found) cout << "找到路線！" << endl;
    else cout << "無法到達目標。" << endl;
}
```

## 4. 字串處理演算法 (String Algorithms)
> 我常用在搜索欄上（但有很多函式庫可以處理了(´･ω･`)
> 雜湊 Hashing 跟要用到 dp 的 LCS 我還不熟
> 這邊都是字串搜索的演算法
> 
### (1) Brute Force（暴力搜尋）
han 暴力，逐一筆對字串格式

#### ● 時間複雜度
平均 $O(n × m)$

#### ● 範例 (c++)
| 參數名稱 | 說明 | 型態 |
|:--|:--|:--|
| `text` | 備搜索的字串 | `string` |
| `t_str` | 要搜索的目標字串 | `string` |
```cpp=
void brute_force(string text, string t_str) {
    int s_len = text.length();
    int t_len = t_str.length();
    
    for (int i=0; i<s_len - t_len +1; i++) {
        int start_index = i, end_index;
        bool match = true;
        for (int j=0; j<t_len; j++) {
            end_index = i+t_len-1;
            if(text[i+j] != t_str[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            printf("找到目標字串位於%d至%d", start_index, end_index);
        }
    }
}
```

### (2) Knuth–Morris–Pratt（KMP）演算法
當失配發生時，利用模式字串本身的資訊(LPS表)，直接跳到下一個可能的匹配位置，而不用退回主字串。
**LPS 表的定義**
>對於模式字串中每個位置 i，
>lps[i] = 該位置前（包含 i）這段字串中，
>最長的「前綴 = 後綴」子字串的長度。

#### ● 時間複雜度
$O(n + m)$

#### ● 範例 (c++)
1. 預先建立 lps 陣列。
2. 用兩個指標：
**i** 指向主字串（text）
**j** 指向模式字串（pattern）
3. 若 **text[i] == pattern[j]**，兩者都往右移。
4. 若**不匹配**：
若 **j != 0** → 讓 j = lps[j - 1]（利用之前的資訊跳轉）。
若 **j == 0** → 只移動 i。


```cpp=
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 建立 LPS 陣列
vector<int> buildLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    // 目前最長前綴後綴長度
    int len = 0; 
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } 
        else {
            if (len != 0) {
                // 回到前一個可能的長度
                len = lps[len - 1]; 
            } 
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP 主搜尋函式
void KMP_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> lps = buildLPS(pattern);
    
    // i -> text, j -> pattern
    int i = 0, j = 0; 
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        
        // 找到匹配
        if (j == m) { 
            printf("找到目標字串位於 %d 至 %d\n", i - j, i - 1);
            // 繼續搜尋下一個
            j = lps[j - 1]; 
        } 
        else if (i < n && text[i] != pattern[j]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    KMP_search(text, pattern);
    return 0;
}
```
### (3) Boyer–Moore 演算法
我覺得最好用的演算法喔，他是由右往左比對。當發生不匹配時，它利用兩個規則：
1. **壞字元規則**（Bad Character Rule）
2. **好尾巴規則**（Good Suffix Rule）

這兩個規則讓它可以一次跳過多個字元，而不是只移動一格，在實際運用上比 KMP 快很多。

#### ● 時間複雜度
平均 $O(n)$

#### ● 範例 (c++)
```cpp=
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define NO_OF_CHARS 256  // ASCII 字元集大小

// 建立壞字元表
void buildBadCharTable(const string& pattern, vector<int>& badChar) {
    int m = pattern.length();
    // 預設所有字元為 -1（代表 pattern 中不存在）
    fill(badChar.begin(), badChar.end(), -1);

    // 紀錄 pattern 中每個字元最後出現的位置
    for (int i = 0; i < m; i++) {
        badChar[(unsigned char)pattern[i]] = i;
    }
}

// Boyer–Moore 主搜尋函式
void boyer_moore_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> badChar(NO_OF_CHARS);
    buildBadCharTable(pattern, badChar);
    
    // 模式字串起始位置在 text 中的偏移量
    int shift = 0; 
    while (shift <= n - m) {
        int j = m - 1;

        // 從右往左比對
        while (j >= 0 && pattern[j] == text[shift + j]) {
            j--;
        }

        if (j < 0) {
            printf("找到目標字串位於 %d 至 %d\n", shift, shift + m - 1);
            // 將 pattern 往右移
            shift += (shift + m < n) ? m - badChar[(unsigned char)text[shift + m]] : 1;
        } else {
            // 根據壞字元表計算要移動的距離
            shift += max(1, j - badChar[(unsigned char)text[shift + j]]);
        }
    }
}

int main() {
    string text = "ABAAABCD";
    string pattern = "ABC";
    boyer_moore_search(text, pattern);
    return 0;
}
```

