【C++】競程筆記（algorithm標頭檔）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
---
分析效率
---
```cpp=
void bubble_sort(int arr[], int n) { // arr: 要排序的陣列，n: 陣列大小
for (int i = 0; i < n - 1; ++i) // n 次運算
for (int j = 0; j < n - i - 1; ++j) // (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2 次運算
if (arr[j] > arr[j + 1]) { // n * (n - 1) / 2 次運算
int tmp = arr[j]; // 至多 n * (n - 1) / 2 次運算
arr[j] = arr[j + 1]; // 至多 n * (n - 1) / 2 次運算
arr[j + 1] = tmp; // 至多 n * (n - 1) / 2 次運算
}
}
```
計算步驟數，來分析程式效率。如上為氣泡排序法，執行步驟為：`n+5*n(n-1)/2 = 5/2*n^2 - 3/2 *n`。
### 時間複雜度（Time Complexity）
---
用 Big-O 表示。
只會表示函數成長趨勢最大的那一個，並且捨棄所有係數跟成長趨勢緩慢的項數。
泡沫排序法的 Big-O 如：O(n^2)。
### 快速計算時間複雜度
---
如泡沫排序法就是迴圈執行 n 次，判斷式檢查 n 次。
所以就是 O(n^2)。
### 空間複雜度（Space Complexity）
---
記憶體空間的使用程度。假設宣告一個長度為 n 的陣列，則其空間複雜度至少為 O(n)。
### 質數判斷
---
```cpp=
bool is_prime(int n) {
if (n == 1) return false;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0) return false;
return true;
}
```
n == 1：O(1)
for 迴圈：因為 i 平方 <= n，所以等價於 i <= sqrt(n)，就是兩邊開平方根。-> O(根號n)
n%i == 0：O(1)
return true：O(1)
所以總共時間複雜度是：`O(1) + O(根號n)*O(1) = O(根號n)`
基礎排序法
---
1. 選擇排序法（Selection Sort）
```cpp=
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
```
時間複雜度：O(n²)
空間複雜度：O(1)
swap(a, b)：交換 a、b 兩數值。
原理：剛開始先選擇最小索引元素當作最小值下去比較，那這個由我們自己定義的「最小值」，就要出發去找序列裡面真正的最小值，然後跟他做交換。之後這個最小值就不動，接下來索引 1 開始尋找倒數二小值，這樣一直重複下去。
2. 插入排序法（Insertion Sort）
```cpp=
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
```
時間複雜度：平均情況和最壞情況下為 `O(n²)`；最佳情況（即陣列已經排序）下，時間複雜度為 O(n)。
空間複雜度：O(1)，因為該算法只使用了常數級別的額外空間。
原理：從最小索引元素開始，遍歷比較每個元素，有元素比它小，就插入到它前面去，以此類推。
3. 泡沫排序法（Bubble Sort）
```cpp=
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
bool swapped;
do {
swapped = false;
for (int i = 1; i < n; ++i) {
if (arr[i - 1] > arr[i]) {
std::swap(arr[i - 1], arr[i]);
swapped = true;
}
}
--n;
} while (swapped);
}
```
時間複雜度：O(n²)
空間複雜度：O(1)
原理：前後比對，互相交換，小的在前面，大的在後面。
### 計數排序法
---
```cpp=
void counting_sort(int a[], int n) {
static int cnt[C + 1]; // 計數用的陣列
for (int i = 1; i <= n; ++i) {
++cnt[a[i]];
}
int current = 0; // 現在排到第幾個位置
for (int i = 0; i <= C; ++i)
while (cnt[i] > 0) {
// 這個數字還有剩
a[++current] = i;
--cnt[i];
}
}
```
C 為陣列中元素數量。
時間複雜度：`O(n+C)`
空間複雜度：`O(C)`
### 前綴和（Prefix-Sum）
---
假設一個序列 `a[4] = {1,2,3,4}`，則它前綴和對應的序列為 P。
`P[0] = a[0]`
`P[1] = a[0] + a[1]`
`P[2] = a[1] + a[2]`
`P[3] = a[2] + a[3]`
所以 `P[4] = {1,3,5,7}`
我們可以得到以下這條式子：
`a[n-1] = a[n-2] + a[n-1]` 設 n 為陣列長度，且當索引等於 0 時，`P[0] = a[0]`。
以下是 Prefix-Sum 的圖解：
Image Source：https://rishabh1000khandelwal.medium.com/parallel-prefix-sum-scatter-and-gather-d6d7323c03a1
計數排序的原理其實就是基於 Prefix-Sum 而來的，所以以下是計數排序進階寫法：
```cpp=
struct Data {
int key;
Custom_Type something_else;
};
void advance_counting_sort(Data a[], int n) {
static int cnt[C + 1]; // 計數用的陣列
static Data result[N + 1];
for (int i = 1; i <= n; ++i) // 計數
++cnt[a[i].key];
for (int i = 1; i <= C; ++i) // 前綴和
cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; --i) // 從每個數字的尾端開始往前放
result[cnt[a[i].key]--] = a[i];
for (int i = 1; i <= n; ++i)
a[i] = result[i];
for (int i = 0; i <= C; ++i) // 清空計數陣列
cnt[i] = 0;
}
```
algorithm 標頭檔
---
需引入標頭檔：
```cpp
#include <algorithm>
```
大部分 methods 遵循以下語法：
```cpp
algorithm_name(container.begin(), container.end(), ...);
```
container 是一個容器物件。
begin() 和 end() 是容器的成員函數，回傳指向容器開始和結束的迭代器（iterator）。
### sort()
---
對容器中的元素進行排序。
時間複雜度：O(nlogn)
語法：`sort(container.begin(), container.end(), compare_function);`
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
vector<int> n = {5, 2, 9, 1, 5, 6};
sort(n.begin(), n.end());
for (int num : n){
cout << num << " ";
}
return 0;
}
```
`std::partial_sort`：區間排序，前 n 個元素有序。
```cpp
// 示範, 可自行調整
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
```
`std::stable_sort`：穩定排序，保留相等元素的相對順序。
```cpp
std::stable_sort(vec.begin(), vec.end());
```
### sort() 中的 compare_function
---
預設 `sort()` 都是升序排序（由小到大），若要降序排序（由大到小），則需要自訂函數：
```cpp=
bool cmp(int x, int y) {
return x > y; // true or false
}
```
然後就可以放在 `sort()` 最右邊，這樣就升序了：
```cpp=
sort(container.begin(), container.end(), cmp);
```
加入 `struct` 結構體寫法：
```cpp=
struct Data {
int key;
Custom_Type something_else;
};
bool cmp(Data a, Data b) {
return a.key < b.key;
}
```
### 搜尋演算法
---
函數：`find()`
在容器中尋找與給定值相符的第一個元素。
語法：
```cpp
auto it = find(container.begin(), container.end(), value);
```
若有找到，it 將指向匹配的元素；如果沒有找到，it 將等於 `container.end()`。
註：it 就是 iterator，迭代器。
```cpp=
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> numbers = {1, 2, 3, 4, 5};
auto it = find(numbers.begin(), numbers.end(), 3);
if (it != numbers.end()) {
cout << "Found: " << *it << endl;
} else {
cout << "Value not found." << endl;
}
return 0;
}
```
因為 iterator 本身是一個記憶體空間的位址，所以加上 `*` Dereference 運算子，讓值顯示出來。
`std::binary_search`：對有序區間進行二分搜。
```cpp=
std::sort(vec.begin(), vec.end()); // 二分搜前置條件：資料要先排序好
bool found = std::binary_search(vec.begin(), vec.end(), 4);
```
`std::find_if`：找出第一個符合特定條件的元素。
```cpp
auto it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 3; });
```
這條的意思是：在 `vec` 容器中尋找第一個大於 3 的元素。
後面 `[](int x) { return x > 3; }` 為 lambda 運算式。表接收一個參數 x，若 x > 3 則回傳 true，否則 false。
同樣的，若找不到 `it` 就 = `vec.end()`。
### copy()
---
將一個範圍內的元素複製到另一個容器或陣列。
語法：
```cpp
copy(source_begin, source_end, destination_begin);
```
```cpp=
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> source = {1, 2, 3, 4, 5};
int destination[5]; // 空陣列
copy(source.begin(), source.end(), destination);
for (int i = 0; i < 5; ++i) {
cout << destination[i] << " ";
}
return 0;
}
```
輸出結果：
```
1 2 3 4 5
```
### equal()
---
比較兩個容器或兩個範圍內的元素是否相等。
語法：
```cpp
bool result = equal(first1, last1, first2);
// or
bool result = equal(first1, last1, first2, compare_function);
```
```cpp=
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {1, 2, 3, 4, 5};
bool are_equal = std::equal(v1.begin(), v1.end(), v2.begin());
std::cout << (are_equal ? "Vectors are equal." : "Vectors are not equal.") << std::endl;
return 0;
}
```
輸出結果：
```
Vectors are equal.
```
### reverse()
---
反轉區間內的元素順序。
語法：
```cpp
std::reverse(vec.begin(), vec.end());
```
### fill()
---
將指定區間內的所有元素指定為某個值。
語法：
```cpp
std::fill(vec.begin(), vec.end(), 0); // 所有元素設為 0
```
### replace()
---
將區間內的某個值替換為另一個值。
語法：
```cpp
std::replace(vec.begin(), vec.end(), 1, 99); // 將所有 1 替換為 99
```
### swap()
---
兩互相交換元素。
語法：
```cpp
swap(a, b); // a, b 值會對調
```
### min()、max()
---
回傳最小或最大的值。
語法：
```cpp
min(a, b);
max(a, b);
// or
min({a, b, c}); // 比較多種元素, 使用大括號
max({a, b, c});
```
### min_element(first, last)、max_element(first, last)
---
尋找容器或陣列中最小或最大的元素。
語法：
```cpp=
auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());
```
但要記得，如果要求值的話在前面加上 `*`，如：`*min_it` or `*std::min_element(vec.begin(), vec.end());`。
### nth_element(first, nth_pos, last)
---
尋找容器中第 k 小的數字。也用於對指定範圍內的元素進行部分排序，但不會完全排序。
語法：
```cpp
nth_element(StartIterator, NthIterator, EndIterator);
```
NthIterator：指向範圍內第 n 個位置的迭代器，要放正確元素的位置。
```cpp=
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
// 尋找第 5 小的元素（即索引為 4 的元素）
nth_element(vec.begin(), vec.begin() + 4, vec.end());
cout << "第 5 小的元素是：" << vec[4];
return 0;
}
```
輸出結果：
```
第 5 小的元素是：3
```
平均時間複雜度為 O(n)；最壞情況為 O(n^2)，n 是範圍內的元素數量。
### unique(first, last)
---
將容器中相鄰重複元素過濾到只剩單一個元素存在。
```cpp=
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> vec = {1, 2, 2, 3, 3, 3, 4, 5, 5};
// 移除相鄰的重複元素
auto it = unique(vec.begin(), vec.end());
// 刪除多餘的元素
vec.erase(it, vec.end());
for (int n : vec) {
cout << n << ' ';
}
}
```
### 小結（總表）
---
| 函式 | 描述 | 語法 |
|---|---|---|
| `sort()` | 對容器中的元素進行排序 | `sort(container.begin(), container.end(), compare_function);` |
| `partial_sort()` | 只排序前 n 個元素 | `std::partial_sort(vec.begin(), vec.begin() + n, vec.end());` |
| `stable_sort()` | 穩定排序，保留相等元素的相對順序 | `std::stable_sort(vec.begin(), vec.end());` |
| `find()` | 搜尋第一個匹配的元素 | `auto it = find(container.begin(), container.end(), value);` |
| `binary_search()` | 在已排序的容器中執行二分搜 | `std::binary_search(vec.begin(), vec.end(), value);` |
| `find_if()` | 搜尋符合條件的第一個元素 | `auto it = std::find_if(vec.begin(), vec.end(), condition);` |
| `copy()` | 複製一個範圍內的元素到另一個容器 | `copy(source_begin, source_end, destination_begin);` |
| `equal()` | 比較兩個範圍內的元素是否相等 | `bool result = equal(first1, last1, first2);` |
| `reverse()` | 反轉區間內的元素順序 | `std::reverse(vec.begin(), vec.end());` |
| `fill()` | 將區間內的所有元素設定為某個值 | `std::fill(vec.begin(), vec.end(), value);` |
| `replace()` | 將區間內的某個值替換為另一個值 | `std::replace(vec.begin(), vec.end(), old_value, new_value);` |
| `swap()` | 交換兩個變數的值 | `std::swap(a, b);` |
| `min()` / `max()` | 回傳最小或最大的值 | `min(a, b);` 或 `max(a, b);` |
| `min_element()` / `max_element()` | 找出最小或最大元素的迭代器 | `auto min_it = std::min_element(vec.begin(), vec.end());` |
| `nth_element()` | 找出第 k 小的元素，部分排序 | `nth_element(vec.begin(), vec.begin() + k, vec.end());` |
| `unique()` | 移除相鄰的重複元素 | `auto it = unique(vec.begin(), vec.end()); vec.erase(it, vec.end());` |
numeric 標頭檔
---
要使用此標頭檔前需要引入標頭檔：
```cpp
#include <numeric>
```
主要用於數值運算的標頭檔，會用就能夠少掉幾行程式碼的撰寫。
### accumulate()
---
`accumulate()` 用於計算容器中所有元素的總和，原始作法是 for 迴圈遍歷。
語法：
```cpp
accumulate(Iter first, Iter last, T init);
```
Iter first：迭代器起始點。
Iter last：迭代器終點。
T init：預設值。
```cpp=
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3, 4, 5};
int sum = accumulate(v.begin(), v.end(), 0);
cout << "Sum: " << sum;
return 0;
}
```
輸出結果：
```
Sum: 15
```
### iota(first, last, val);
---
於給定的序列容器範圍中填入一段連續的數字。
簡單來說像是：
```cpp
for (int i = 0;i<n;i++){
a[i] = i;
}
```
只是簡化成一行：`iota(a.begin(), a.end(), 0);`
```cpp=
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main() {
vector<int> v(5); // 空 vector
iota(v.begin(), v.end(), 1); // 填空連續數字進去 vector
for (int i : v) {
cout << i << " ";
}
return 0;
}
```
輸出結果：
```
1 2 3 4 5
```
### gcd()
---
算最大公因數。
```cpp=
#include <iostream>
#include <numeric>
using namespace std;
int main() {
int a = 48;
int b = 18;
int result = gcd(a, b); // 算 48, 18 的最大公因數
cout << "GCD: " << result;
return 0;
}
```
輸出結果：
```
GCD: 6
```
### lcd()
---
算最小公倍數。
最小公倍數公式：`LCM(a, b) = |a * b| / GCD(a, b)`（在不用函數的情況下）
```cpp=
#include <iostream>
#include <numeric>
using namespace std;
int main() {
int a = 48;
int b = 18;
int result = lcm(a, b);
cout << "LCM: " << result;
return 0;
}
```
輸出結果：
```
LCM: 144
```
Sign in with Wallet
Connect another wallet