分治演算法（Divide and Conquer）#
分治法是遞迴的高階應用，核心思想是庖丁解牛（Chunk it up）：將大問題拆解為若干個互不相關的子問題，分別解決後合併結果。
分治三步驟#
- Divide（分）：將大問題拆解成若干個子問題
- Conquer（治）：分別解決這些子問題
- Merge（合）：將子問題的結果合併成原問題的解
這與分散式系統中的 MapReduce 思想如出一轍。
分治程式碼模板#
def divide_conquer(problem, param1, param2, ...):
# 1. Terminator (終止條件)
if problem is None:
return result
# 2. Prepare & Split (準備資料/拆分問題)
data = prepare_data(problem)
subproblems = split_problem(problem, data)
# 3. Conquer Subproblems (解決子問題)
subresult1 = divide_conquer(subproblems[0], p1, ...)
subresult2 = divide_conquer(subproblems[1], p1, ...)
subresult3 = divide_conquer(subproblems[2], p1, ...)
# 4. Merge (合併結果)
result = merge(subresult1, subresult2, subresult3, ...)
# 5. Revert States (清理狀態，如需要)
return result分治的適用條件#
分治法適用的前提是子問題互不相關。如果子問題有重疊（如費氏數列），則不應使用標準分治，而應考慮動態規劃。
經典案例#
案例一：Pow(x, n) - LeetCode 50#
計算 x 的 n 次方。
| 方法 | 時間複雜度 | 空間複雜度 | 說明 |
|---|---|---|---|
| 暴力法 | O(n) | O(1) | 迴圈乘 n 次 |
| 分治法（遞迴） | O(log n) | O(log n) | 遞迴堆疊開銷 |
| 快速冪（迭代） | O(log n) | O(1) | 面試最優解 |
分治邏輯：
- 若 n 為偶數：x^n = (x^(n/2))^2
- 若 n 為奇數：x^n = (x^(n/2))^2 * x
n 可能是負數，需先將 x 轉為 1/x，n 轉為正數。
快速冪（位運算版本）
def myPow(x, n):
if n < 0:
x = 1 / x
n = -n
result = 1
while n > 0:
if n & 1: # 最後一位是 1
result *= x
x *= x # 基底翻倍
n >>= 1 # 右移一位
return result原理： 將 n 視為二進位表示，每個位元對應 x 的 2^0, 2^1, 2^2… 次方。
案例二：求眾數 - LeetCode 169#
找出陣列中出現次數大於 n/2 的元素。
| 方法 | 時間複雜度 | 說明 |
|---|---|---|
| 暴力法 | O(n^2) | 兩層迴圈計數 |
| 雜湊表 | O(n) | 空間換時間 |
| 排序法 | O(n log n) | 排序後取中間 |
| 分治法 | O(n log n) | 左右分別求眾數再比較 |
分治邏輯：
- Divide：將陣列切分為左右兩半
- Conquer：遞迴求出左右兩邊的眾數
- Merge：
- 若左右眾數相同，直接返回
- 若不同，計算兩者在當前區間的出現次數，返回較多者
分治解法程式碼
def majorityElement(nums):
def majority(lo, hi):
# 終止條件：區間長度為 1
if lo == hi:
return nums[lo]
# 分
mid = (lo + hi) // 2
left = majority(lo, mid)
right = majority(mid + 1, hi)
# 合
if left == right:
return left
# 計數比較
left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left)
right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right)
return left if left_count > right_count else right
return majority(0, len(nums) - 1)分治 vs 遞迴#
| 特性 | 遞迴 | 分治 |
|---|---|---|
| 本質 | 程式設計技巧 | 演算法策略 |
| 子問題關係 | 可能重疊 | 互不相關 |
| 結果處理 | 直接返回 | 需要合併 |
| 平行化 | 通常不適合 | 非常適合 |
分治法的子問題之間沒有依賴關係，因此非常適合平行計算（Parallel Processing）。