【C++】競程筆記（algorithm標頭檔）

分析效率

1
2
3
4
5
6
7
8
9
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)。

質數判斷

1
2
3
4
5
6
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）
1
2
3
4
5
6
7
8
9
10
11
12
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 開始尋找倒數二小值，這樣一直重複下去。

  1. 插入排序法（Insertion Sort）
1
2
3
4
5
6
7
8
9
10
11
12
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)，因為該算法只使用了常數級別的額外空間。

原理：從最小索引元素開始，遍歷比較每個元素，有元素比它小，就插入到它前面去，以此類推。

  1. 泡沫排序法（Bubble Sort）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)

原理：前後比對，互相交換，小的在前面，大的在後面。

計數排序法

1
2
3
4
5
6
7
8
9
10
11
12
13
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

Image Source：https://rishabh1000khandelwal.medium.com/parallel-prefix-sum-scatter-and-gather-d6d7323c03a1

計數排序的原理其實就是基於 Prefix-Sum 而來的，所以以下是計數排序進階寫法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 標頭檔

需引入標頭檔：

1
#include <algorithm>

大部分 methods 遵循以下語法：

1
algorithm_name(container.begin(), container.end(), ...);

container 是一個容器物件。

begin() 和 end() 是容器的成員函數，回傳指向容器開始和結束的迭代器（iterator）。

sort()

對容器中的元素進行排序。

時間複雜度：O(nlogn)

語法：sort(container.begin(), container.end(), compare_function);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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 個元素有序。

1
2
// 示範, 可自行調整
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

std::stable_sort：穩定排序，保留相等元素的相對順序。

1
std::stable_sort(vec.begin(), vec.end());

sort() 中的 compare_function

預設 sort() 都是升序排序（由小到大），若要降序排序（由大到小），則需要自訂函數：

1
2
3
bool cmp(int x, int y) {
    return x > y; // true or false
}

然後就可以放在 sort() 最右邊，這樣就升序了：

1
sort(container.begin(), container.end(), cmp);

加入 struct 結構體寫法：

1
2
3
4
5
6
7
8
struct Data {
    int key;
    Custom_Type something_else;
};
 
bool cmp(Data a, Data b) {
    return a.key < b.key;
}

搜尋演算法

函數：find()

在容器中尋找與給定值相符的第一個元素。

語法：

1
auto it = find(container.begin(), container.end(), value);

若有找到，it 將指向匹配的元素；如果沒有找到，it 將等於 container.end()。

註：it 就是 iterator，迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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：對有序區間進行二分搜。

1
2
std::sort(vec.begin(), vec.end());  // 二分搜前置條件：資料要先排序好
bool found = std::binary_search(vec.begin(), vec.end(), 4);

std::find_if：找出第一個符合特定條件的元素。

1
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()

將一個範圍內的元素複製到另一個容器或陣列。

語法：

1
copy(source_begin, source_end, destination_begin);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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
1 2 3 4 5

equal()

比較兩個容器或兩個範圍內的元素是否相等。

語法：

1
2
3
4
5
bool result = equal(first1, last1, first2);

// or

bool result = equal(first1, last1, first2, compare_function);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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;
}

輸出結果：

1
Vectors are equal.

reverse()

反轉區間內的元素順序。

語法：

1
std::reverse(vec.begin(), vec.end());

fill()

將指定區間內的所有元素指定為某個值。

語法：

1
std::fill(vec.begin(), vec.end(), 0); // 所有元素設為 0

replace()

將區間內的某個值替換為另一個值。

語法：

1
std::replace(vec.begin(), vec.end(), 1, 99); // 將所有 1 替換為 99

swap()

兩互相交換元素。

語法：

1
swap(a, b); // a, b 值會對調

min()、max()

回傳最小或最大的值。

語法：

1
2
3
4
5
6
7
min(a, b);
max(a, b);

// or
    
min({a, b, c}); // 比較多種元素, 使用大括號
max({a, b, c});

min_element(first, last)、max_element(first, last)

尋找容器或陣列中最小或最大的元素。

語法：

1
2
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 小的數字。也用於對指定範圍內的元素進行部分排序，但不會完全排序。

語法：

1
nth_element(StartIterator, NthIterator, EndIterator);

NthIterator：指向範圍內第 n 個位置的迭代器，要放正確元素的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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;
}

輸出結果：

1
第 5 小的元素是：3

平均時間複雜度為 O(n)；最壞情況為 O(n^2)，n 是範圍內的元素數量。

unique(first, last)

將容器中相鄰重複元素過濾到只剩單一個元素存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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 標頭檔

要使用此標頭檔前需要引入標頭檔：

1
#include <numeric>

主要用於數值運算的標頭檔，會用就能夠少掉幾行程式碼的撰寫。

accumulate()

accumulate() 用於計算容器中所有元素的總和，原始作法是 for 迴圈遍歷。

語法：

1
accumulate(Iter first, Iter last, T init);

Iter first：迭代器起始點。

Iter last：迭代器終點。

T init：預設值。

1
2
3
4
5
6
7
8
9
10
11
12
#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;
}

輸出結果：

1
Sum: 15

iota(first, last, val);

於給定的序列容器範圍中填入一段連續的數字。

簡單來說像是：

1
2
3
for (int i = 0;i<n;i++){
    a[i] = i;
}

只是簡化成一行：iota(a.begin(), a.end(), 0);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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
1 2 3 4 5

gcd()

算最大公因數。

1
2
3
4
5
6
7
8
9
10
11
12
#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;
}

輸出結果：

1
GCD: 6

lcd()

算最小公倍數。

最小公倍數公式：LCM(a, b) = |a * b| / GCD(a, b)（在不用函數的情況下）

1
2
3
4
5
6
7
8
9
10
11
12
#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;
}

輸出結果：

1
LCM: 144