[algorithms] Divide and Conquer 分治法

視覺化概覽

graph TD
    A["[38, 27, 43, 3]"] -->|分解| B["[38, 27]"]
    A -->|分解| C["[43, 3]"]
    B -->|分解| D["[38]"]
    B -->|分解| E["[27]"]
    C -->|分解| F["[43]"]
    C -->|分解| G["[3]"]
    D -->|合併| H["[27, 38]"]
    E -->|合併| H
    F -->|合併| I["[3, 43]"]
    G -->|合併| I
    H -->|合併| J["[3, 27, 38, 43]"]
    I -->|合併| J

    style D fill:#FFD700
    style E fill:#FFD700
    style F fill:#FFD700
    style G fill:#FFD700
    style J fill:#90EE90

什麼是分治法？

分治法將大問題分解為小問題，遞迴解決後合併結果。

         原問題
        /      \
    子問題1    子問題2
    /    \    /    \
  更小  更小  更小  更小
    \    /    \    /
    合併結果  合併結果
        \      /
        最終答案

三步驟

1. 分解（Divide）：將問題分成子問題
2. 解決（Conquer）：遞迴解決子問題
3. 合併（Combine）：合併子問題的解

經典範例

歸併排序

void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
 
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);       // 左半
    mergeSort(arr, mid + 1, right);  // 右半
    merge(arr, left, mid, right);    // 合併
}

[38, 27, 43, 3, 9, 82, 10]
    /                    \
[38, 27, 43]       [3, 9, 82, 10]
  /       \          /          \
[38] [27, 43]    [3, 9]    [82, 10]
      /    \      /   \      /    \
    [27]  [43]  [3]  [9]  [82]  [10]
      \    /      \   /      \    /
    [27, 43]    [3, 9]    [10, 82]
        \        /            /
    [27, 38, 43]    [3, 9, 10, 82]
            \          /
    [3, 9, 10, 27, 38, 43, 82]

最大子陣列和

// 分治法求最大子陣列和
int maxSubArray(int[] nums, int left, int right) {
    if (left == right) return nums[left];
 
    int mid = (left + right) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossMax = maxCrossing(nums, left, mid, right);
 
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

快速冪

// O(log n) 計算 base^exp % mod
long power(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        exp >>= 1;
        base = base * base % mod;
    }
    return result;
}

逆序對計數

[2, 4, 1, 3, 5]
逆序對: (2,1), (4,1), (4,3) → 共 3 個

利用歸併排序過程中計算：
左右合併時，右邊元素先出 → 左邊剩餘元素都是逆序對

QuickSelect 第 K 大

找第 2 大 = 找第 (n-2) 小
使用 partition 分區：
[3, 2, 1, | 5 | 6, 4]
           pivot=5
左邊有 3 個 < 5
如果 k < 3 → 在左半找
如果 k == 3 → 就是 5
如果 k > 3 → 在右半找

主定理（Master Theorem）

對於 T(n) = aT(n/b) + O(n^d)：

條件	複雜度
d < log_b(a)	O(n^(log_b(a)))
d = log_b(a)	O(n^d log n)
d > log_b(a)	O(n^d)

常見例子：

• 歸併排序：T(n) = 2T(n/2) + O(n) → O(n log n)
• 二分搜尋：T(n) = T(n/2) + O(1) → O(log n)
• 快速冪：T(n) = T(n/2) + O(1) → O(log n)

分治 vs 動態規劃

	分治	動態規劃
子問題	獨立	重疊
記憶化	不需要	需要
方向	自頂向下	可自底向上

經典題目

1. 歸併排序 - 經典分治
2. 快速排序 - 分區 + 遞迴
3. 最大子陣列和 - LeetCode 53
4. Pow(x, n) - LeetCode 50
5. 第 K 大元素 - LeetCode 215
6. 逆序對 - 劍指 Offer 51
7. 最近點對 - 計算幾何經典
8. 大整數乘法 - Karatsuba

相關檔案

• Java 實作：DivideAndConquer.java