---
# System prepended metadata

title: 【C++】競程筆記（algorithm標頭檔）
tags: [程式設計, C++, 競程, 演算法, CP]

---

【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](https://hackmd.io/_uploads/HJberZjokl.png)

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
```