# 演算法筆記
**把我開發專案時常用(也有不常用但覺得很屌的)的演算法記錄下來，雖然都很基礎但很好用（但還是函式庫香**
## 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;
}
```
Sign in with Wallet
Connect another wallet