【C++】競程筆記（分治法 D&C）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

Introducing Divide and Conquer

Divide and Conquer 英翻中為分治法，這是一個把大問題切分成多個子問題，最後從這些子問題合併來求得主問題解答的一種方法。

而 Divide and Conquer 的步驟主要有三項：

  1. Divide：把原問題拆成多個小且類似的子問題，直到無法再細分。
  2. Conquer：用遞迴解決這些子問題；若遇到規模足夠小的「基本情況（base case）」，則直接輸出答案。
  3. Merge：合併子問題得到最終解，一旦較小的子問題被解決，則遞迴合併所有子問題得到更大問題的答案。

例題：王老先生

Problem Source：https://tioj.sprout.tw/problems/114

題目敘述：

有個正方形土地 $N \times N$ ， $N$ 為 $2$ 的正整數次方。

有一格子 $(X, Y)$ 已被王老先生選走了，你要放 $\frac{N \times N - 1}{3}$ 個 3 格的 L 型方塊來填滿剩餘的地。滿足積木都互不重疊、放在沒有被挖掉的格子上，且鋪滿所有沒被選走的地方。

解法：

把這塊土地劃分成 $(N / 2) \times (N / 2)$ 的地，如下示意圖的紅色切割線：

image

假設灰色那塊是被選走的，則可以發現能夠輕易地擺上一塊 L 型積木。

image

放好了第一塊積木之後，你可能會抓破頭腦，不知道該怎麼擺放，放一放有可能會像下面的情形：

image

ok，那麼何妨試試放一塊跨區域的積木呢？如下所示。

image

那這樣的情形就會變成每個 $(N / 2)$ 區塊都會有像是灰色格子的情形了，接下來就可以依序填滿：

image

Divide and Conquer 的精神就要準備體現在這了，我們在較小子問題得出了答案，那理所當然的，後續更大的答案也能用這樣的方式解決。比如說 $N = 8$ 的情形。

image

一樣將這 $8 \times 8$ 的網格切成四個 $4 \times 4$ 的區域，那這樣子就是四種剛剛的子問題了，一樣都放上橫跨三個區域的 L 型積木，即可完成這 $8 \times 8$ 網格的問題。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#include "lib0114.h"
using namespace std;

namespace {
    // 以 (x, y) 為左上角、邊長 size 內鋪滿 L 型積木
    // (sx, sy) 為特殊格座標（1-base 全域座標）
    void tile(int x, int y, int size, int sx, int sy) {
        if (size == 1) return; // 1x1 special case

        int mid = size / 2;
        int cx = x + mid - 1;  // 中心左上格的 x
        int cy = y + mid - 1;  // 中心左上格的 y

        // 四象限是否含特殊格
        bool inTL = (sx <= cx && sy <= cy);
        bool inTR = (sx >  cx && sy <= cy);
        bool inBL = (sx <= cx && sy >  cy);
        bool inBR = (sx >  cx && sy >  cy);

        // 四個靠中心的格子
        int tlx = cx,     tly = cy; // 中間靠左
        int trx = cx + 1, try_ = cy; // 中間靠右
        int blx = cx,     bly = cy + 1; // 中間下一格靠左
        int brx = cx + 1, bry = cy + 1; // 中間下一格靠右

        // 於中心放一個 L 型積木，覆蓋不含原始特殊格的那三格
        // 若 true 表示碰到特殊格，直接回傳答案
        if (inTL) {
            Report(trx, try_, blx, bly, brx, bry);
        } else if (inTR) {
            Report(tlx, tly, blx, bly, brx, bry);
        } else if (inBL) {
            Report(tlx, tly, trx, try_, brx, bry);
        } else { // inBR
            Report(tlx, tly, trx, try_, blx, bly);
        }

        // 對四象限遞迴，三個象限用剛放下的中心格作為「人造特殊格」（如本文上方解法）
        // TL
        tile(x, y, mid,
             inTL ? sx : tlx,
             inTL ? sy : tly);
        // TR
        tile(x + mid, y, mid,
             inTR ? sx : trx,
             inTR ? sy : try_);
        // BL
        tile(x, y + mid, mid,
             inBL ? sx : blx,
             inBL ? sy : bly);
        // BR
        tile(x + mid, y + mid, mid,
             inBR ? sx : brx,
             inBR ? sy : bry);
    }
}

void solve(int N, int X, int Y) {
    tile(1, 1, N, X, Y);
}

分割與合併

如剛才例題的王老先生，那是屬於分治法的基本範疇，透過不斷切割子問題，直到不能再切為止，而在較小的子問題中得到解，之後就可將這些子問題各自解決，合併成大問題的解。

Merge Sort 是 Divide and Conquer 中最經典的應用，流程大致如下：

  1. Divide：將長度為 $n$ 的陣列二分（ $n / 2$ ）為兩個子陣列。
    • 若子陣列長度為 $1$ ，則表示原本的陣列就已經排好了。
  2. Conquer：將左右子陣列分別遞迴呼叫 Merge Sort，直到陣列長度為 $1$ 。
  3. Combine：將兩個已經排序好的子陣列合併（Merge）成一個完整排序的陣列。

註：Divide 是遞迴函數的內部邏輯，而 Conquer 為執行呼叫遞迴的行為，需注意這邊很容易混淆。

先來看程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return; // 表示陣列中只有一個元素，連排都不用排

    // (right - left) 避免 int overflow
    int mid = left + (right - left) / 2; // 二分法

    // 遞迴處理左半與右半子陣列
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    
    // 臨時子陣列
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left; // i 指向 L，j 指向 R，k 指向 arr

    // Combine
    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) { // 代表左邊元素較小，先放
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    // 若 L 或 R 尚有剩餘元素，直接加入
    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];
}

以下是 Merge Sort 的遞迴樹圖（From Merge Sort (With Code in Python/C++/Java/C)）：

merge-sort-example_0

分割的時間複雜度為 $O(1)$ ，為常數時間，就是那條 int mid = left + (right - left) / 2;。

遞迴處理的時間複雜度為 $O(\frac{n}{2}) + O(\frac{n}{2}) + O(n)$ ，因為要處理左右兩個長度被切一半的子陣列，另外再加合併兩子陣列的時間成本 $O(n)$ 。

但其實並沒那麼簡單，看遞迴樹圖就知道這東西有分很多層需要去做遞迴處理，所以在不斷分割之下，拆到長度剩 1 的時間複雜度為：

  • 第一層： $2O(\frac{n}{2})$
  • 第二層： $4O(\frac{n}{4})$
  • 第三層： $8O(\frac{n}{8})$
  • 第 k 層： $2^k \cdot O(\frac{n}{2^k})$

最後變成 $2^k \cdot O(\frac{n}{2^k}) + k \cdot O(n)$ ，只取最高次項，因此最後每層所花時間為 $O(n)$ 。

另外每次遞迴呼叫時，就會分割長度 $n / 2$ ，所以層數為 $O(log n)$ ，而每層總共需花 $O(n)$ ，因此整體時間複雜度為 $O(n log n)$ 。

例題：逆序數對

Problem Source：https://tioj.ck.tp.edu.tw/problems/1080

這題的解法就是拿合併排序法的解法來解。

當合併時，若左半部數字 $L[i] > R[i]$ ，則：

  • 兩個子陣列皆為遞增數列，表示 $L[i], L[i + 1], \cdots, L[end]$ 都比 $R[j]$ 大。
  • 然後就把逆序數對數量 += 左半部剩下的元素個數。

演算流程大致如下：

  1. 用 mergeSort 遞迴函數排序數列，同時計算逆序數對。
  2. 在合併階段，當左邊元素大於右邊元素時，更新逆序數對數量。
  3. 輸出 Data。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

long long merge_count(vector<int>& arr, vector<int>& temp, int left, int right) {
    
    if (left >= right) return 0;

    int mid = (left + right) / 2;
    ll inv_count = 0;

    // Divide and Conquer : 計算左右兩邊的逆序數
    inv_count += merge_count(arr, temp, left, mid);
    inv_count += merge_count(arr, temp, mid + 1, right);

    // 合併計算左右的逆序數
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inv_count += (mid - i + 1);
        }
    }

    // 把剩下的元素填回去
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int p = left; p <= right; p++) arr[p] = temp[p];

    return inv_count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, case_num = 1;
    while (cin >> n && n != 0) {
        vector<int> arr(n), temp(n);
        for (int i = 0; i < n; i++) cin >> arr[i];

        ll inv_count = merge_count(arr, temp, 0, n - 1);

        cout << "Case #" << case_num++ << ": " << inv_count << "\n";
    }

    return 0;
}

Quick Sort

這也是一個基於 Divide and Conquer 的排序演算法，跟 Merge Sort 有些類似。

首先在 Divide 的部分，要先挑選一個 pivot（基準值），如在陣列 {19, 17, 15, 12, 16, 18, 4, 11, 13} 中，選擇 13 這個 element 作為 pivot。

然後接下來做 Divide，將這個陣列切成小於及大於 pivot 的子陣列。

接下來是 Conquer 遞迴處理：

（左子陣列）

  • {7, 12, 4, 11} 再做一次 Divide 的動作，這邊選 11 作為 pivot。
  • 然後分成 {7, 4}、{12}
  • {12} 不能分了，而 {7, 4} 再繼續分下去（4 選作 pivot） → {7}、{4}

再來右子陣列做的事情跟左子陣列一樣，就不贅述了。

最後做 Combine：每層遞迴結束後，就會自動排好結果了（左子陣列排序結果 + pivot + 右子陣列排序結果）。

如左子陣列 {7, 4} 最後得到的結果會是 {4}、{7}，合併回去的結果會是 {4, 7}。

然後 {4, 7} 再合併 pivot {11} 和右子陣列 {12}，就會是 {4, 7, 11, 12} 了。

以上流程的遞迴樹圖如下所示（
Quick Sort in C | GeeksForGeeks）：

Quick-Sort-Algorithm

時間複雜度分析

分割部分，因為要掃過整個陣列，然後再依據 pivot 去分配左右子陣列，因此這部分的時間複雜度為 $O(n)$ 。

最佳情況：

假設每次取到的 pivot 都剛好把陣列切一半。

每次遞迴呼叫時，就會分割長度 $n / 2$ ，所以層數為 $O(log n)$ ，而每層總共需花 $O(n)$ ，因此最佳情況的時間複雜度為 $O(n log n)$ 。

平均情況：

假設 pivot 是隨機取的。

這邊在做的事情其實跟最佳情況沒什麼差別，分割長度平均都接近 $n / 2$ ，時間複雜度基本上還是 $O(n log n)$ 。

最壞情況：

假設 pivot 每次都取到最大或最小元素。

分割結果是一邊有 $n-1$ 個元素，另一邊是空集合，遞迴深度就變成 $n$ ，再加上每層需花 $O(n)$ ，最後時間複雜度就會是令人咋舌的 $O(n^2)$ 。

範例程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = arr[high]; // 選最後一個元素作為 pivot
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                // arr[j] <= pivot 表示應放在左邊
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]); // 最後把 pivot 放到正確位置
        int pi = i + 1; // 記錄 pivot 的最終位置

        // 遞迴排序 pivot 左右子陣列
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

結論

這是一個靠賽的排序法，選對就能起飛，選錯直接烙賽。