# Coding Note－Algorithm
此篇為針對演算法之筆記整理，此份筆記內容參考至Horowitx.E(2003), Fundamentals of data structure in C, 13th printing及大學開放式課程。除統整學習內容及概念外，也整理常見之問題討論及解析(c++)，希望能夠過此資訊筆記紀錄學習歷程，並精進程式能力！
## Sorting Algorithm
此部分將簡介各排序演算法的運算邏輯、效能、程式碼以及流程圖，並針對其運算的空間、時間複雜度進行分析。下圖即為複雜度的運算性能比較。Ref:Big-O Complexity Chart http://bigocheatsheet.com/
另外，以下關於演算法運算邏輯的演示皆用此組範例資料進行(排序由小到大)
```
A[5] = {25, 15, 6, 18, 42}
排序後即為 A[5] = {6, 15, 18, 25, 42}
```
### Bubble Sort
運算邏輯及簡介:氣泡排序法反覆地遍歷陣列，比較相鄰兩個元素。如果順序錯誤(視期望之排序)，就將它們交換。過程反覆進行，直到整個陣列排序完畢。
Time Complexity:
* Best Case: O(n)
* Average: O(n^2)
* Worst Case: O(n^2)
最壞狀況下，陣列原本是逆著排的，因此n個階層下，須執行n-i-1次(i為外層迴圈迭代次數)。因此，時間複雜度即為(i=0->n−1)∑(n−i−1)=n(n−1)/2
Space Complexity:O(1)
範例測資演示
First pass:
(**25,15**,6,18,42)->(**15,25**,6,18,42) //swap
(15,**25,6**,18,42)->(15,**6,25**,18,42) //swap
(15,6,**25,18**,42)->(15,6,**18,25**,42) //swap
(15,6,18,**25,42**)->(15,6,18,**25,42**)
Second pass:
(**15,6**,18,25,42)->(**6,15**,18,25,42) //swap
(6,**15,18**,25,42)->(6,**15,18**,25,42)
(6,15,**18,25**,42)->(6,15,**18,25**,42)
Third pass:
(**6,15**,18,25,42)->(**6,15**,18,25,42)
(6,**15,18**,25,42)->(6,**15,18**,25,42)
Fourth pass:
(**6,15**,18,25,42)->(**6,15**,18,25,42)
Code
```
void bubble_sort(int *array)
{
for (int i = 0; i < n - 1; i++) //n為size of array
{
for (int j = 0; j < n - i - 1; j++)
{
if (array[j] > array[j + 1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
```
#### Bubble Sort optimized
修正後的氣泡排序法可避免在陣列已經排序後，仍然接續往下面的階層遍歷，節省了多餘的部分。
Code
```
void bubble_sort_revision(int *array)
{
for(int i=0; i<n; i++)
{
flag = false;
for(int j=0; j<n-i-1; j++)
{
if(array1[j]>array1[j+1])
{
flag = true;
int temp = array1[j+1];
array1[j+1] = array1[j];
array1[j] = temp;
}
}
//check whether it's sorted or not
if(!flag){
return;
}
}
}
```
### Quick Sort
運算邏輯及簡介: Quicksort採用的是Divide-and-Conquer策略，Quicksort將在數列中找一個數字作為基準 (pivot)，把該數列中所有比基準數小的數字都放在左邊、比基準數大的數字都放在右邊。接者，再讓左右兩個子陣列各自做排序，當左、右子陣列排完時，整個排序也就結束。
Time Complexity:
* Best Case: O(nlogn)
Best case為pivot恰好將陣列分成切割兩等分(比pivot大以及小的一樣多)
$T(n)=2×T(n/2)+c×n$ //partition time
$=...+n×T(1)+\log_2(n)×c×n$
* Average: O(nlogn)
* Worst Case: O(n^2)
Worst case為pivot恰好為陣列的最大值或是最小值
$T(n)=T(n-1)+T(0)+c×n=T(1)+c×(2+3+...+n)=c×(n+2)(n-1)/2$
Space Complexity:O(logn)
範例測資演示(以首項作為pivot演示)
(25,15,6,18,42)->(15,6,18,25,42) //taking 25 as pivot
* left (15,6,18)->(6,15,18) //taking 15 as pivot
left:(6)->(6) right:(18)->(18) //sorted
* right (42)->(42) //sorted
Combined:(6,15,18,25,42)
Code
```
void Quicksort(vector<pair<int, int>> &A, int left, int right)
{
int l = left + 1, r = right;
if (left >= right)
return;
int pivot = A[left].first;
while (1)
{
while (l <= right)
{
if (A[l].first > pivot)
break;
l++;
}
while (r > left)
{
if (A[r].first < pivot)
break;
r--;
}
if (l > r)
break;
swap(A[l], A[r]);
}
swap(A[left], A[r]);
Quicksort(A, left, r - 1);
Quicksort(A, r + 1, right);
}
```
#### Quicksort revision
優化方法：和Bubble sort revision相同，此優化的目的也是為了避免Worst case的發生，以提升此演算法的效率。詳細計算可見以下資料來源(Ref:https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/)
1. Middle-of-three solution
(1) 令 middle = (left + right) /2
(2) 比較 A[left]、A[middle] 與 A[right] 三筆資料，排出中間 值，將中間值再與 A[left]做交換
(3) 讓現在新的 A[left] 作為 pivot
假設 pivot 位置在 n 筆資料中的 n/10 與 9n/10 之間：
T(n) = c*n + T(n/10) + T(9n/10)
因此，此方法的時間複雜度可以收斂到 O(nlogn)
2. Median-of-Medians solution
(1) 將 n 個資料分成 n/5 個堆，每堆有 5 個資料 (可能會有 1 個堆 的資料不到 5 個) ，花 O(n) 時間。
(2)每堆由小到大做排序。排序一堆花 O(5^2) 時間，可以想成 O(1) 常 數。所以當有 n/5 堆排序時，共花 O(n) 時間。
(3)排序完將每堆中位數資料作為該堆pivot。在這 n/5 堆中，遞迴套 用quicksort，求得中位數 k。 k 即為 median-of-medians ， 此步驟花費時間 T(n/5)。
(4)以 k 作為 pivot 重新將整堆做排序，花 O(n) 時間。
(5)至少有一半的組（不包括 pivot 自己及不到 5 個資料的組）每組將 至少有 3 個資料大於或等於 pivot。這保證了 pivot 𝑘 將陣列分 成兩部分，每部分大小至多為7n/10。
遞迴關係式即為T(n)<=T(n/5)+T(7n/10)+O(n)，因此此方法在 worst case時，時間複雜度仍能降為O(n)。
### Selection Sort
運算邏輯及簡介:選擇排序法將在陣列中尋找最小值，並將其交換至陣列的第一個元素，並將剩餘元素往右推直到所有元素排序完畢。
Time Complexity:
* Best Case: O(n^2)
因每個迴圈中所有元素須被遍歷過，以找出最小值，因此時間複雜度為n^2
* Average: O(n^2)
* Worst Case: O(n^2)
Space Complexity:O(1)
範例測資演示:
(25,15,6,18,42)->(6,25,15,18,42) //將找到的最小值放至左側
(6,25,15,18,42)->(6,15,25,18,42)
(6,15,25,18,42)->(6,15,18,25,42)
(6,15,18,25,42)->(6,15,18,25,42)
Code:
```
#include <bits/stdc++.h>
using namespace std;
void selectionSort(vector<int>& A) {
int n = A.size();
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (A[j] < A[min]) {
min = j;
}
}
swap(A[min], A[i]);
}
}
```
### Insertion Sort
運算邏輯及簡介: Insertion sort將資料列分為已排序及未排序兩部分，每個步驟皆從從未排序資料中，挑選一個元素並將其插入已排序資料中，直到所有資料排序完成。
Time Complexity:
* Best Case: O(n)
最好的情況中，此陣列已排序完成，因此每一遍歷到的元素皆插入至最後即可。
* Average: O(n^2)
* Worst Case: O(n^2)
Space Complexity:O(1)
範例測資演示:
(25,**15**,6,18,42)->(**15**,25,6,18,42) //以25為已排序、剩餘為未排序
(15,25,**6**,18,42)->(**6**,15,25,18,42) //6加入已排序資料
(6,15,25,**18**,42)->(6,15,**18**,25,42) //18加入已排序資料
(6,15,18,**25**,42)->(6,15,18,**25**,42) //插入後順序不變
(6,15,18,25,**42**)->(6,15,18,25,**42**)
Code:
```
void insertionSort(vector<int>& A) {
int n = A.size();
for (int i = 1; i < n; ++i) {
int key = A[i];
int j = i - 1;
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j]; //move bigger elements back
j = j - 1;
}
A[j + 1] = key; //move key into the sorted section
}
}
```
### Merge Sort
運算邏輯與簡介: Merge sort 採用Divide and Conquer，將資料對半切分直到每個子陣列僅含一個元素（即已排序），再將子陣列依序合併、排序（子陣列首元素較小的排於前），直到資料列重組完成。
Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn)
Space Complexity:O(n)
```
void merge(vector<int>& A, int left, int mid, int right) {
vector<int> L(A.begin() + left, A.begin() + mid + 1);
vector<int> R(A.begin() + mid + 1, A.begin() + right + 1);
int i = 0, j = 0, k = left;
while (i < L.size() && j < R.size()) {
if (L[i] <= R[j]) A[k++] = L[i++];
else A[k++] = R[j++];
}
while (i < L.size()) A[k++] = L[i++];
while (j < R.size()) A[k++] = R[j++];
}
void mergeSort(vector<int>& A, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(A, left, mid);
mergeSort(A, mid + 1, right);
merge(A, left, mid, right);
}
```
### Heap Sort
運算邏輯與簡介: Heap sort 利用 Heap Tree 的資料結構來排序，先將資料構建成最大堆（Max Heap），此時根節點為最大值。接著將根節點（最大值）與最後一個節點交換，並從堆中移除，再對剩下的資料重新調整為最大堆，重複此過程直到結束。
*原地排序法、不須其他空間，且非穩定排序
Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn)
Space Complexity:O(1)
```
void heapify(vector<int>& A, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && A[left] > A[largest]) largest = left;
if (right < n && A[right] > A[largest]) largest = right;
if (largest != i) {
swap(A[i], A[largest]);
heapify(A, n, largest); // 遞迴調整子樹
}
}
void heapSort(vector<int>& A) {
int n = A.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapify(A, n, i);
// 將堆頂元素與最後一個元素交換，並調整剩餘堆
for (int i = n - 1; i > 0; i--) {
swap(A[0], A[i]);
heapify(A, i, 0);
}
}
```
### C++ STL sorting
運算邏輯及簡介: C++之函式庫 algorithm 中，即包含 std::sort 的功能，時間複雜度是 O(nlogn)，相較於初階演算法的小，且使用上也較高階演算法容易許多。關於STL的細節可見資料結構篇。
解析: 此函數在 C++ 中使用一種稱為 Introsort (a varient of Quicksort)，結合了QuickSort、InsertionSort及Heapsort以達到較好的performance。Introsort 設計為在QuickSort超過一定遞歸深度時切換至Heapsort，確保在最壞情況時間複雜度保持在 O(N log N)，避免Quicksort最壞情況下 O(N^2) 複雜度。
Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn)
Space Complexity:O(logn)
Usage
```
sort(begin,end,function);
```
其中funciton可為自定義之函數，可視情況定義想要排序的依據。
Examle:Using compare function
```
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> //for abs function
using namespace std;
bool compare(int a, int b){
return abs(a) < abs(b);
}
int main() {
vector<int> ex = {-9, 3, -5, 1, -4, 7, -2, 6, 8};
sort(ex.begin(), ex.end(),compare);
cout << "Sorted vector by absolute value: ";
for(int num : ex)
cout << num << " ";
cout << "\n";
return 0;
}
```
## Searching Algorithm
### Linear Search (Sequential search)
運算邏輯及簡介:一種基本運用BruteForce的方法，逐一遍歷所有資料，直到找到預搜尋的目標為止
Time Complexity: O(n)
Space Complexity: O(1)
Code
```
int linearSearch(const vector<int>& A, int key) {
for (int i = 0; i < A.size(); ++i) {
if (A[i] == key)
return i;
}
return -1; //not find
}
```
### Binary Search
運算邏輯及簡介: 將資料排序後，取中間值並判斷欲尋找的數字大於或是小於中間值，再一層一層反覆向下找，當範圍的左右兩邊收斂到相等時，此即為欲尋找的數字位置。
Time Complexity: O(logn)
Space Complexity: O(1)-迭代, O(logn)-遞歸
範例資料演示:
Code
```
int binarySearch(const vector<pair<int, int>> &A, int low, int high, int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (A[mid].first == key)
return A[mid].second;
if (A[mid].first < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
```
#### Revision－Interpolation Search
優化方法: 改進的二分搜尋，適用於均勻分佈的排序數組。插值演算法估計目標元素可能出現的位置，並根據此猜測進行搜尋。
Time Complexity:
* Best Case: O(loglogn)
* Worst Case: O(n)
Space Complexity: O(1)
範例資料演示:
Code
```
int interpolationSearch(const vector<int>& A, int key) {
int low = 0, high = A.size() - 1;
while (low <= high && key >= A[low] && key <= A[high]) {
if (low == high)
if (A[low] == key) return low;
//guess the possible position
int pos = low + ((double)(high - low) / (A[high] - A[low])) * (x - A[low]);
if (A[pos] == x)
return pos;
else if (A[pos] < x)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
```
### Jump Search
運算邏輯及簡介: 跳著間續檢查元素，而非逐一線性搜尋。從第 √n 個元素開始，每次跳 √n 個元素，直到找到比目標大的元素，然後在上一跳的區間內線性搜尋。此方法適用於資料量大、但無法使用二分搜尋的情況。
Time Complexity: O(sqrt(n))
Space Complexity: O(1)
Code:
```
int jumpSearch(const vector<int>& A, int key) {
int n = A.size();
int step = sqrt(n);
int prev = 0;
// 找到大於等於 key 的區塊
while (A[min(step, n) - 1] < key) {
prev = step;
step += sqrt(n);
if (prev >= n) return -1;
}
// 線性搜尋該區塊
while (A[prev] < key) {
prev++;
if (prev == min(step, n)) return -1;
}
if (A[prev] == key) return prev;
return -1;
}
```
## Greedy Method
此部分統整幾個常見的貪心演算法問題，針對題目討論解題策略及思路分析。
### Minimum Spanning Tree(MST)
問題簡介：最小生成樹是圖中一棵包含所有節點、且邊的總權重最小的生成樹，不包含任何環，並確保節點間保持連通。
#### Kruskal's method
運算邏輯與方法：將所有邊依權重排序，並使用並查集判斷是否形成環，如果加入新的邊不會形成環，則將該邊加入最小生成樹（MST）並合併集合，重複直到選到𝑛-1條邊。（針對一個n個點的圖）
應用：適合邊少的圖，先排序邊再逐步加入。
```
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int par[mxn];
int sz[mxn];
void init()
{
for (int i = 0; i < mxn; i++)
{
par[i] = i;
sz[i] = 1;
}
}
int find(int x)
{
if (par[x] == x)
return x;
return par[x] = find(par[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (x == y)
return;
if (sz[y] < sz[x])
swap(x, y);
par[x] = y;
sz[y] += sz[x];
}
struct Edge
{
int u, v, w;
};
bool cmp(Edge a, Edge b)
{
return a.w < b.w;
}
int main()
{
int n, m;
while (cin >> n >> m)
{
vector<Edge> vec;
init();
for (int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
vec.push_back({a, b, w});
}
int cnt = n - 1;
sort(vec.begin(), vec.end(), cmp);
long long ans = 0;
for (Edge e : vec)
{
if (find(e.u) != find(e.v))
{
merge(e.u, e.v);
ans += e.w;
cnt--;
}
}
if (cnt != 0)
cout << -1 << '\n';
else
cout << ans << '\n';
}
}
```
#### Prim's method
運算邏輯與方法：選定起始點，並用優先佇列維護權重最小者。每次從優先佇列取出最小邊，若該邊的終點未在 MST 中，將新點加入，並將其所有鄰接邊加入優先佇列，直到所有節點都包含於其中。
應用:適合點多的圖，從一點開始擴展 MST。
```
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
vector<pair<int, int>> adj[mxn]; // {neighbor, weight}
bool visited[mxn];
long long prim(int start, int n) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
long long total_weight = 0;
int count = 0;
while (!pq.empty() && count < n) {
auto [w, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;
total_weight += w;
count++;
for (auto [v, wt] : adj[u]) {
if (!visited[v])
pq.push({wt, v});
}
}
if (count < n) return -1; // 圖不連通
return total_weight;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
cout << prim(0, n) << endl;
}
```
### Interval Scheduling Problem
問題簡介：Interval Scheduling是一種在存在大量區間的情況下，有效率地找出一組最大相容子集（Largest Compatible Subset）的演算法。（即資源最大化的概念）
方法：排列結束時間，選擇結束時間較早的活動，逐一遍歷活動，重複直到結束。
Code：
```
#include <bits/stdc++.h>
using namespace std;
struct Activity {
int start, end;
};
bool cmp(Activity a, Activity b) {
return a.end < b.end;
}//compare the ending time
int intervalScheduling(vector<Activity>& activities) {
sort(activities.begin(), activities.end(), cmp); //sort by ending time
int count = 0, currentTime = 0;
for (const auto& act : activities) {
if (act.start >= currentTime) { //check if valid or not
count++;
currentTime = act.end;
}
}
return count;
}
int main() {
int n;
cin >> n;
vector<Activity> acts(n);
for (int i = 0; i < n; i++)
cin >> acts[i].start >> acts[i].end;
cout << intervalScheduling(acts) << endl;
}
```
## Dynamic Programming
將主要問題拆解為小問題後，找出遞迴關係，一步步往回推解決主要問題，常用於解決最佳化問題。
### Optimal Substructure
概念:大問題的答案，不用重新計算，而從子問題的答案中將大問題答案給尋找並拼湊出來。可分為以下兩步驟，包括子問題的數量，及子問題不同的分類可能。
### Overlapping subproblems
概念:子問題持續在重複，反覆相同的運算，即可得出大問題的解答
### Bottom-up
運算邏輯與方法:找出遞迴關係式後，找出計算順序來避免遞迴以完成
算法。
以階梯問題為例
```
#include<bits/stdc++.h>
using namespace std;
int main(){
int F[100000];
int n;
cin>>n;
F[1] = 1, F[2] = 2;
for(int i=3; i<=n; i++){
F[i] = F[i-1] + F[i-2];
}
cout<<F[n];
return 0;
}
```
### Top-down Memoization
運算邏輯與方法:不找計算順序，而是直接依照遞迴關係式找遞迴，並以memo(備忘錄)紀錄以計算過的資料，以增加撰寫的容易程度。
以階梯問題為例
```
#include<bits/stdc++.h>
using namespace std;
int F[100] = {0};
int stair(int n){
if(F[n]>0) return F[n]; //check memo
F[n] = stair(n-1) + stair(n-2); //record to memo
return F[n];
}
int main(){
int n;
cin>>n;
F[1] = 1, F[2] = 2;
cout<<stair(n);
return 0;
}
```
---
以下為幾個常見的DP問題
### Knapsack problem (0/1背包問題)
原敘述: 有n種物品，物品j的重量為w_j，價值為p_j。假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W，試得到在承重的最大重量內可裝的最大價值。
剖析: 此題的命名之所以為0-1是因為每種物品只能選擇0個或1個，不能夠分割，因此無法適用Greedy Method，只放單位價值最高的物品可能會捨去其餘總和更大的情況。(fractional knapsack problem即適用)
動態規劃(二維)解法
```
dp[i][j]:限重j的情況，放入1~i的物品之最大價值
W[i]第i個物品重量、V[i]第i個物品價值
if(j>=W[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
else
dp[i][j]=dp[i-1][j];
```
限重大於等於第i物品的情況下，第i個物品即有可能放入背包中，因此比較不放此物品及放入此物品後之價值比較，選擇最大值即為此情況下之最佳解。反之，若無法放入此物品，即為i-1時之值。
以下以i=4, j=5繪製表格dp舉例
W={0,1,2,4,5}, V={0,3,2,8,5}
| i/j | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --| - |- |-- |-- |-- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 3 | 3 | 5 | 5 | 5 |
| 3 | 0 | 3 | 3 | 5 | 8 |11 |
| 4 | 0 | 3 | 3 | 5 | 8 |11 |
### LCS（Longest Common Subsequence）
方法:假設有三字串分別為A={a~1~, a~2~,....,a~i~}, B={b~1~, b~2~,....,b~j~}, C={c~1~, c~2~,....,c~k~}，其中目標為在AB字串中找到最大的共用字串，而假設字串C為兩者的共用字串。從最後的字母開始討論，逐一推至完整數列，共可分為以下三種情況:
1. a~i~=b~j~
若最後一個字元相同，則只需考慮A~i-1~及B~j-1~
3. a~i~!=b~j~且c~k~!=a~i~
如果A與C字串的最後一個字不同，則共同字串必在B~j~及A~i-1~之間
4. a~i~!=b~j~且c~k~!=b~j~
如果A與B字串的最後一個字不同，則共同字串必在A~j-1~及A~i~之間
此三種情況即為子問題的三種可能，接下來只需表格化在A及B各元素間
表格化字串共同數列，假設兩字串A、B分別為A={X,Y,Z,X,Y,X},B={Y,Z,X,Z,Y,X}，有兩
依此規則可繪製成以下圖表
| i/j | 0 | 1(X) | 2(Y) | 3(Z) | 4(X) | 5(Y) | 6(X) |
|------|-----|------|------|------|------|------|------|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1(Y) | 0 | 0 | 1 | 1 | 1 | 2 | 2 |
| 2(Z) | 0 | 0 | 1 | 2 | 2 | 2 | 2 |
| 3(X) | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
| 4(Z) | 0 | 1 | 1 | 2 | 3 | 3 | 3 |
| 5(Y) | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
| 6(X) | 0 | 1 | 2 | 2 | 3 | 4 | 5 |
Sign in with Wallet
Connect another wallet