[Algorithm] 分而治之法

演算法概念

分而治之（Divide and Conquer）的三步驟：

1. Divide：把大問題切成幾個規模較小、結構相同的子問題。
2. Conquer：對每個子問題遞迴求解，小到不能再切時直接解。
3. Combine：把子問題的解合起來變成原問題的解。

關鍵是「合起來」——沒有合起來就不是分治，是淘汰。淘汰切完只進其中一塊、其他丟掉；分治切完每塊都要解，最後再合回去。

典型遞迴式 $T(n) = a \, T(n/b) + f(n)$：$a$ 是子問題個數、$b$ 是子問題規模相對原問題縮幾倍、$f(n)$ 是合併成本。Combine 決定整體效率——合併做到 $O(n)$ 就能配上 $T(n) = 2T(n/2) + O(n) = O(n \log n)$，合併若變成 $O(n \log n)$ 整體就退化到 $O(n \log^2 n)$。

適合分治的條件：子問題之間獨立（不獨立就要動態規劃）、合併成本合理（通常要 $O(n)$ 或更低）。

各適用情境

合併排序（Merge Sort）

演算法策略

Divide：從中間切成左右兩半。Conquer：各自遞迴排序。Combine：兩個已排序的小陣列用雙指標合併——各指一個最左元素，誰小先寫進結果，相等時優先取左邊（保穩定性）。

複雜度

每層合併 $O(n)$、共 $\log n$ 層 → $T(n) = 2T(n/2) + O(n) = O(n \log n)$。不論輸入如何都這麼快。代價是要 $O(n)$ 額外空間。

範例

題目：[38, 27, 43, 3, 9, 82, 10] 從小到大排序。

圖解：

步驟：

Divide 階段：一路切半到單元素。

Combine 階段：由下往上兩兩合併。

第 3 → 2 層：

第 2 → 1 層：

第 1 → 0 層：合併 [3, 27, 38, 43] + [9, 10, 82]，雙指標細節：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))


def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

快速排序（Quick Sort）

演算法策略

跟合併排序是分治的鏡像：Divide 昂貴（挑 pivot 後原地用雙指標重排、左邊都 $\leq$ pivot、右邊都 $\geq$ pivot），Combine 便宜（什麼都不做——原地分好就排好了）。

Hoare partition 的流程（pivot = a[left]）：

• 左指標 $i$：從 left+1 起往右，停在 a[i] >= pivot 的位置。
• 右指標 $j$：從 right 起往左，停在 a[j] <= pivot 的位置。
• 如果 i < j 就 swap（兩個站錯邊）；如果 i >= j 就跳出外層、做 swap(a[left], a[j])，pivot 就定位。

複雜度

平均 pivot 切出接近均等的兩半 → $T(n) = 2T(n/2) + O(n) = O(n \log n)$。最壞 pivot 每次都極值、一邊空一邊 $n - 1$ → $T(n) = T(n - 1) + O(n) = O(n^2)$。實務用隨機 pivot 或三數取中（median-of-three）避免 worst case。

範例

題目：[25, 10, 35, 5, 30, 15]（1-indexed）排序。

步驟：

第一層 Quick_Sort(1, 6)：pivot = a[1] = 25，$i = 1$、$j = 7$。

跳出後 swap(a[1], a[4]) → [5, 10, 15, 25, 30, 35]。pivot 25 落在位置 4。左半 (1, 3)、右半 (5, 6)。

第二層左 Quick_Sort(1, 3)：[5, 10, 15]，pivot = 5。$i$ 停在 2、$j$ 走到 1，swap(a[1], a[1]) 不動。

第三層 Quick_Sort(2, 3)：[10, 15]，pivot = 10。$i$ 停在 3、$j$ 走到 2，swap(a[2], a[2]) 不動。

第二層右 Quick_Sort(5, 6)：[30, 35]，pivot = 30，同理不動。

最終 [5, 10, 15, 25, 30, 35]。整個過程沒有 Combine——partition 原地分、遞迴回來就排好。

另一種看法：每次 partition 完成的快照

上面那張表追的是 partition 內部的 i/j 小輪。換個粒度——只記每次 partition 完成、pivot 落定的瞬間：

下表【 】框住待處理子陣列、left/right 指下一次 partition 的範圍：

每一列到下一列就是一次完整 partition（內部小輪都被吞進去）。pivot 落定後就不再動，剩下的子陣列各自遞迴；單元素子陣列直接回傳、不畫列。

def quick_sort(a, left, right):
    if left >= right:
        return
    pivot = a[left]
    i, j = left, right + 1
    while True:
        while True:
            i += 1
            if i > right or a[i] >= pivot:
                break
        while True:
            j -= 1
            if a[j] <= pivot:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
        else:
            break
    a[left], a[j] = a[j], a[left]
    quick_sort(a, left, j - 1)
    quick_sort(a, j + 1, right)

二維平面上的極點

演算法策略

極點（maximal point）：若 $x_1 > x_2$ 且 $y_1 > y_2$，則 $P_1$ 宰制 $P_2$。沒被任何人宰制的點就是極點。所有極點排起來是一條「往右下的階梯」。

分治招式：

1. Divide：按 x 中位數切成左半 $L$（小 x）、右半 $R$（大 x）。
2. Conquer：各自遞迴求 $L_{max}$、$R_{max}$。
3. Combine：
   • $R_{max}$ 的每點 x 都大於 $L$ 全部 → 不可能被 $L$ 宰制 → 全保留。
   • $L_{max}$ 裡的點要跟 $R$ 比 y——令 $y^* = \max\{y : (x, y) \in R_{max}\}$（就是 $R_{max}$ 的最大 y），$L_{max}$ 裡 $y > y^*$ 保留、$y \leq y^*$ 丟掉。

為什麼只比 $R_{max}$ 的最大 y 就夠？因為 $R_{max}$ 裡最大 y 的那個點本身一定是極點，它能宰制的範圍就是 $R$ 裡最廣的——它都打不贏的 $L$ 點，其他 $R$ 點也打不贏。

極點跟凸包不是同一回事：凸包關心「最外圍輪廓」（上下左右都算）、極點只關心「右上角」。

複雜度

每層合併掃一遍 $O(n)$、共 $\log n$ 層 → $T(n) = 2T(n/2) + O(n) = O(n \log n)$。若輸入未排序，初始按 x 排序也是 $O(n \log n)$。

範例

題目：8 個點（已按 x 排序）$P_1 = (1, 6), P_2 = (2, 8), P_3 = (3, 4), P_4 = (4, 7), P_5 = (5, 3), P_6 = (6, 5), P_7 = (7, 1), P_8 = (8, 2)$。

圖解：

步驟：中位 x 切半，$L = \{P_1, P_2, P_3, P_4\}$、$R = \{P_5, P_6, P_7, P_8\}$。

遞迴 $L$：切成 $\{P_1, P_2\}$ 和 $\{P_3, P_4\}$。

合併：右半 $\{P_4\}$ 的 $y^* = 7$，左半 $\{P_2\}$ 中 $P_2.y = 8 > 7$ 保留 → $L_{max} = \{P_2, P_4\}$。

遞迴 $R$：同理求得 $R_{max} = \{P_6, P_8\}$。

最後合併：$R_{max}$ 最大 y = 5（$P_6$）。$L_{max}$ 中 $P_2.y = 8 > 5$、$P_4.y = 7 > 5$ 都保留。最終極點 $\{P_2, P_4, P_6, P_8\}$。座標 $(2, 8) \to (4, 7) \to (6, 5) \to (8, 2)$，y 遞減階梯。

def maximal_points(points):
    pts = sorted(points, key=lambda p: p[0])

    def solve(a):
        if len(a) == 1:
            return a
        mid = len(a) // 2
        L = solve(a[:mid])
        R = solve(a[mid:])
        y_star = max(p[1] for p in R)
        L_keep = [p for p in L if p[1] > y_star]
        return L_keep + R

    return solve(pts)

最接近的兩點（Closest Pair）

演算法策略

平面 $n$ 點，找距離最近的一對。Naive 兩兩配對 $O(n^2)$。分治能壓到 $O(n \log n)$——關鍵在 Combine 的巧思。

1. 預先按 x 排序。
2. Divide：中位 x 切左右半 $P_L$、$P_R$。
3. Conquer：$d_L = \text{closest}(P_L)$、$d_R = \text{closest}(P_R)$、$d = \min(d_L, d_R)$。
4. Combine：檢查跨越中垂線的點對。

Combine 若兩兩配對會爆成 $O(n^2)$，得想辦法剪枝。

Strip（中垂線帶）：以中垂線 $x = x_m$ 為中心、左右各 $d$ 寬的直立帶子，寬度 $2d$；形式定義 $\text{strip} = \{P : |P.x - x_m| < d\}$。

關鍵直覺：離中垂線超過 $d$ 的點，光 x 軸距離就 $\geq d$，不可能和任何另一點配出 $< d$ 的距離——整個跳過。所以只用 strip 內的點繼續配對。

strip 裡的點按 y 排序後，每個點只需往下檢查最多 7 個就夠——strip 寬 $2d$、左右兩側內部最近距離都 $\geq d$，幾何上 $d \times 2d$ 的矩形至多容 8 個點。下方範例的 ClosestPairDiagram 從第 5 步起會把 strip（藍色帶狀區）疊在中垂線兩側。

複雜度

每層 Combine $O(n)$（strip 篩 + y 排序 + 每點掃 ≤ 7）、共 $\log n$ 層 → $T(n) = 2T(n/2) + O(n) = O(n \log n)$。實作技巧：遞迴過程中同時維護 x 和 y 兩份預排序索引，避免每層重排 strip 退化成 $O(n \log^2 n)$。

範例

題目：6 個點 $A = (1, 3), B = (2, 1), C = (3, 4), D = (5, 2), E = (6, 5), F = (8, 3)$。

圖解：

步驟：

Divide：中位 x ≈ 4，左半 [A, B, C]、右半 [D, E, F]。

左半（3 點直接兩兩算）：

$d_L \approx 2.24$。

右半：

$d_R \approx 2.83$。$d = \min(d_L, d_R) = 2.24$。

Combine：中垂線 $x_m = 4$，strip 收 $|x - 4| < 2.24$，即 $x \in (1.76, 6.24)$ → $B, C, D, E$。按 y 排序：$B(1) \to D(2) \to C(4) \to E(5)$。

每個點往下檢查 y 差 < 2.24 的：

沒更短的 → 最近距離 $\approx 2.24$（$AB$ 或 $AC$）。

import math


def closest_pair(points):
    pts = sorted(points, key=lambda p: p[0])

    def dist(p, q):
        return math.hypot(p[0] - q[0], p[1] - q[1])

    def solve(a):
        if len(a) <= 3:
            return min((dist(a[i], a[j]) for i in range(len(a)) for j in range(i + 1, len(a))), default=float('inf'))
        mid = len(a) // 2
        xm = a[mid][0]
        d = min(solve(a[:mid]), solve(a[mid:]))
        strip = sorted([p for p in a if abs(p[0] - xm) < d], key=lambda p: p[1])
        for i in range(len(strip)):
            for j in range(i + 1, min(i + 8, len(strip))):
                if strip[j][1] - strip[i][1] >= d:
                    break
                d = min(d, dist(strip[i], strip[j]))
        return d

    return solve(pts)

快速傅立葉轉換（FFT）

演算法策略

DFT（Discrete Fourier Transform，離散傅立葉轉換）：把長度 $n$ 的序列 $[a_0, a_1, \ldots, a_{n-1}]$ 換成另一串 $[A_0, A_1, \ldots, A_{n-1}]$。沒新增、沒減少資訊，只是同一筆資料換個視角看（小寫 $a$ 是輸入、大寫 $A$ 是轉換後輸出，下同）。FFT（Fast Fourier Transform）是 DFT 的快速計算法，把時間從 $O(n^2)$ 壓到 $O(n \log n)$。

最經典的應用是多項式乘法：兩個 $n$ 次多項式直接相乘 $O(n^2)$；若先各自 FFT 變成「點值表示」，乘法就退化成點對點相乘 $O(n)$，再用反向 FFT（IFFT）轉回係數，總共 $O(n \log n)$，比直接乘快很多。

兩個小道具：$i$ 與 $\omega$

$i$ 是虛數單位，定義 $i^2 = -1$；自乘四次轉一圈：

$\omega$ 是「$n$ 次單位根」（$n$-th root of unity），FFT/DFT 挑來代入計算的特殊複數，定義 $\omega = e^{-i \cdot 2\pi/n}$。$n = 4$ 時 $\omega = -i$，$\omega$ 表跟 $i$ 表幾乎一樣（差個負號）：

關鍵性質：$\omega$ 自乘 $n$ 次就轉一圈回到 $\omega^0 = 1$，所以指數對 $n$ 取餘數即可查表（$\omega^4 = \omega^0$、$\omega^5 = \omega^1$⋯⋯）。

DFT 公式：

拆白話：

• $k$（output index）：第幾個輸出，共 $n$ 個 $A_k$ 各跑一次。
• $j$（input index）：輸入編號，把 $a_0, \ldots, a_{n-1}$ 各乘一個 $\omega^{jk}$ 再加起來。
• $\omega^{jk}$：$jk$ 對 $n$ 取餘後查上表。

每個 $A_k$ 就是「把所有 $a_j$ 各乘一個從表查到的數，全部加起來」。

FFT 的加速觀察：DFT 公式直接展開要 $O(n^2)$。把奇偶下標拆兩組會出現重複計算，分治下去得 $T(n) = 2T(n/2) + O(n) = O(n \log n)$。具體流程是 Cooley–Tukey butterfly 遞迴，手算考題很少要求展開到這層；考試多半要的是用 DFT 公式硬代，FFT 是程式實作時才寫的。

複雜度

多項式乘法的整體流程：

關鍵就是「換視角後乘法變便宜」——直接係數相乘 $O(n^2)$，繞點值一圈反而 $O(n \log n)$。

範例

題目：對 $[a_0, a_1, a_2, a_3] = [0, 1, 2, 3]$ 做 DFT，$n = 4$。

步驟：先記好 $\omega$ 表 $\omega^0 = 1,\ \omega^1 = -i,\ \omega^2 = -1,\ \omega^3 = i$，然後逐個 $A_k$ 套公式。

$A_0$（$k = 0$）：每項都乘 $\omega^0 = 1$，全部加起來。

$A_1$（$k = 1$）：

$A_2$（$k = 2$）：$jk = 0, 2, 4, 6$，對 $4$ 取餘 → $0, 2, 0, 2$。

$A_3$（$k = 3$）：$jk = 0, 3, 6, 9$，對 $4$ 取餘 → $0, 3, 2, 1$。

結果：

import numpy as np


def poly_multiply(A, B):
    n = 1
    while n < len(A) + len(B) - 1:
        n *= 2
    A_hat = np.fft.fft(A, n)
    B_hat = np.fft.fft(B, n)
    C = np.fft.ifft(A_hat * B_hat).real
    return [round(x) for x in C[:len(A) + len(B) - 1]]


print(poly_multiply([1, 2, 3], [4, 5]))  # [4, 13, 22, 15]

常見考法

下一篇動態規劃——當子問題不再獨立、彼此重疊時，分治會重複計算，DP 用「記下來不再重算」解掉這個低效。