Divide and Conquer

預備知識

Recursion

分治法（Divide and Conquer）是一種把大問題拆成好幾個相同類型的小問題，各自解決之後，再把結果合併回大問題答案的策略。

白話理解

想像要幫全班改考卷，一個人改要花很久。於是把考卷分成好幾疊，找好幾位小老師分別批改（拆解），每疊改完後再統一登記到成績單上（合併）。這種「拆開、各自處理、再合起來」的做法，就是分治法的精神。

它本身不算是一個具體演算法，而是一種思考框架，很多經典演算法都是建立在這個框架之上，例如 Merge Sort、Quick Sort、Binary Search 與 Quickselect。

三個步驟

Divide（分解）：把原問題拆成幾個規模較小、性質相同的子問題。
Conquer（解決）：遞迴地解決每個子問題，直到子問題小到可以直接得出答案（Base Case）。
Combine（合併）：把子問題的答案組合起來，變成原問題的答案。

solve(問題) {
  if (問題已經夠小 / Base Case) {
    直接回傳答案
  }

  子問題們 = divide(問題)                 // 1. Divide
  子答案們 = 子問題們.map(solve)           // 2. Conquer（遞迴呼叫自己）
  return combine(子答案們)               // 3. Combine
}

看起來是不是很眼熟？沒錯，分治法本質上就是應用在特定場景下的 Recursion，差別在於它特別強調「合併小答案」這個步驟。

範例：用分治法找出陣列中的最大值

題目：在一堆數字裡找出最大值（雖然這題直接用迴圈掃一遍就能解決，但很適合拿來理解分治法的拆解與合併過程）。

Python
JavaScript
Java

def find_max(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    # Base Case：只剩一個元素，它自己就是這個範圍的最大值
    if left == right:
        return arr[left]

    mid = (left + right) // 2

    # Divide + Conquer：分別遞迴找出左右兩半各自的最大值
    left_max = find_max(arr, left, mid)
    right_max = find_max(arr, mid + 1, right)

    # Combine：兩邊的最大值再比一次，就是整個範圍的最大值
    return max(left_max, right_max)

function findMax(arr, left = 0, right = arr.length - 1) {
  // Base Case：只剩一個元素，它自己就是這個範圍的最大值
  if (left === right) return arr[left];

  const mid = Math.floor((left + right) / 2);

  // Divide + Conquer：分別遞迴找出左右兩半各自的最大值
  const leftMax = findMax(arr, left, mid);
  const rightMax = findMax(arr, mid + 1, right);

  // Combine：兩邊的最大值再比一次，就是整個範圍的最大值
  return Math.max(leftMax, rightMax);
}

class Solution {
    static int findMax(int[] arr, int left, int right) {
        // Base Case：只剩一個元素，它自己就是這個範圍的最大值
        if (left == right) return arr[left];

        int mid = (left + right) / 2;

        // Divide + Conquer：分別遞迴找出左右兩半各自的最大值
        int leftMax = findMax(arr, left, mid);
        int rightMax = findMax(arr, mid + 1, right);

        // Combine：兩邊的最大值再比一次，就是整個範圍的最大值
        return Math.max(leftMax, rightMax);
    }

    static int findMax(int[] arr) {
        return findMax(arr, 0, arr.length - 1);
    }
}

逐步拆解：以 `[3, 7, 2, 9, 4]` 為例

findMax([3, 7, 2, 9, 4])                         範圍 [0, 4]
  ├─ findMax 左半：範圍 [0, 2] → [3, 7, 2]
  │    ├─ findMax 左半：範圍 [0, 1] → [3, 7]
  │    │    ├─ findMax 範圍 [0, 0] → 3（Base Case）
  │    │    └─ findMax 範圍 [1, 1] → 7（Base Case）
  │    │    Combine：max(3, 7) = 7
  │    └─ findMax 範圍 [2, 2] → 2（Base Case）
  │    Combine：max(7, 2) = 7
  └─ findMax 右半：範圍 [3, 4] → [9, 4]
       ├─ findMax 範圍 [3, 3] → 9（Base Case）
       └─ findMax 範圍 [4, 4] → 4（Base Case）
       Combine：max(9, 4) = 9

最後 Combine：max(7, 9) = 9

可以看到，問題不斷被「Divide」成更小的範圍，直到剩下一個元素（Base Case），接著再一層一層「Combine」往上合併，最終得到整體答案 9。

複雜度

分治法的時間複雜度取決於「拆成幾份」與「合併的成本」，常見的幾種組合：

演算法	拆解方式	合併成本	總時間複雜度
Binary Search	每次丟掉一半，只往一邊繼續找	O(1)	O(log n)
Merge Sort	每次切一半，兩邊都要繼續處理	O(n)（合併兩個排序好的陣列）	O(n log n)
Quickselect	每次只往答案所在的那一半繼續找	O(n)（Partition）	平均 O(n)

新手小提醒

不是所有分治法都是 O(n log n)！

關鍵要看「拆成幾份繼續處理」與「合併要花多少時間」，上面這張表就是很好的對照。