分治法跟 DP 長得很像——都是「把大問題拆成小問題」。差別在哪？分治的子問題不重疊，所以不需要 memo。Merge Sort 是分治，費波那契是 DP。搞混這兩個，面試會扣分。
先講結論
分治三步：拆開（Divide）→ 各自解決（Conquer）→ 合併結果（Combine）。關鍵在第三步——怎麼合併。Merge Sort 的合併是 O(n)，所以整體 O(n log n)。如果合併是 O(n²)，那分治就沒有意義了。
Merge Sort：分治的教科書範例
[38, 27, 43, 3]
↓ 拆
[38, 27] [43, 3]
↓ ↓
[38] [27] [43] [3]
↓ ↓ 合併
[27, 38] [3, 43]
↓ 合併
[3, 27, 38, 43]
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); // 重點在這
}拆成兩半：T(n/2) + T(n/2)。合併：O(n)。套主定理 → O(n log n)。
快速冪：分治的效率極致
O(log n) 算 base^exp，因為 x^10 = x^8 × x^2。把指數用二進位拆解，每次平方。
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^10 = 2^(1010₂) = 2^8 × 2^2 = 256 × 4 = 1024
只需要 4 次乘法而不是 10 次
密碼學裡的 RSA 就靠快速冪。沒有它，大數的模冪運算根本不實際。
最大子陣列和
分治解法：最大子陣列要嘛在左半、要嘛在右半、要嘛跨越中間。
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);
}不過坦白說，這題用 Kadane’s Algorithm（DP）O(n) 就能解，分治法 O(n log n) 反而慢。面試問的話我會先寫 Kadane，然後提分治解法當加分。
逆序對
[2, 4, 1, 3, 5]
逆序對: (2,1), (4,1), (4,3) → 共 3 個
暴力 O(n²)。分治：在 Merge Sort 的合併過程中，右邊的元素先出列時，左邊剩餘的元素都跟它構成逆序對。O(n log n)。
這是一個「在已有的分治框架（Merge Sort）上附帶計算」的經典技巧。
QuickSelect：找第 K 大
不需要完全排序，只需要找到第 K 大的元素。
用 Quick Sort 的 partition，每次只往一邊遞迴。平均 O(n)，最差 O(n²)。
找第 3 小，pivot 把陣列分成：
[小的, 小的, 小的 | pivot | 大的, 大的]
左邊有 3 個 → pivot 就是第 4 小
3 < 4 → 往左邊找
主定理（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) |
常用例子：
- Merge Sort：2T(n/2) + O(n) → a=2, b=2, d=1 → O(n log n)
- 二分搜尋：T(n/2) + O(1) → a=1, b=2, d=0 → O(log n)
面試不太考主定理的推導，但能用它秒判分治演算法的複雜度，會讓你看起來很專業。
分治 vs DP
| 分治 | DP | |
|---|---|---|
| 子問題 | 獨立、不重疊 | 重疊、會重複 |
| 是否記憶 | 不需要 | 需要（memo/表格） |
| 代表 | Merge Sort、QuickSelect | 費波那契、背包 |
分治法就像剝洋蔥——不對，那是遞迴。分治法像切披薩：切開、每塊各自處理、再拼回來。重點是切得均勻，不然有人吃到的 pizza 特別大塊。（a.k.a. 不平衡分割導致最差情況）