本文為交通大學開放式課程上課心得整理。
分治法與數學歸納法之間的關聯非常強，因此在開始介紹演算法之前，要先整理一點觀念。
數學歸納法
所有的數學歸納法證明都包含兩個步驟：basis step 以及 inductive step，basis step 是比較簡單的例子，在極小的問題維度之下提出圓滿的解決方法，inductive step 則根據 basis step 展開，讓問題放大之後套用前述邏輯也能正確處理問題。inductive step 的證明方式有兩種：
・weak induction：先假設演算法在步驟 k 的時候是正確的，再往前推進一步證明 k + 1 也是正確的，以此證明所有的 n 都會是正確的。
・strong induction：與 weak induction 相反，strong induction 每次前進的步驟不見得都是一，也可能一次橫跨許多步驟，直接假設演算法在 ≤ k 的時候都是正確的，並證明 k + 1 時也是正確的。
Divide and conquer
Divide and conquer 基本上分成三個部分，divide、conquer 以及 combine，divide 指的是將整個問題切小，但必須確保問題的題型是一樣的；完成之後再將每個小部分都以遞迴（recursive）的方式處理，這就是 conquer，最後再把每個小部分都結合起來（combine），即是最終答案。
以下介紹幾個使用 Divide and conquer 操作的問題（在資料結構有敘述的部分會略過不再重複紀錄）：
Merge Sort
給定一串數字，將數字按照大小排序好之後回傳。
divide 與 conquer 的時間是固定可以算出的，因此演算法的最終目標是要在 O(n) 的時間內完成 combine，讓時間可以 bound 在 O(n log n) 上。
在 merge 時，我們會先開一個額外的空間，將已經排序好的兩個部分抄下來，最後再寫回去。由於切開的兩個部分各自已經排序好，因此可以假設最小／大的元素會在第一個，此時只要比較第一個元素，將比較小／大的放入暫存空間中，再依序往下比較，即可得到完整排序好的陣列，時間複雜度為 O(n)。
在時間複雜度的表現上， merge sort 與 heap sort 是一樣好的，設計者可以自行判斷使用時機。當資料形式很單純（如陣列），可以用 index 抓到資料時，便可以使用 heap sort；反之如果輸入的資料比較複雜（如 linked list），那便可以考慮使用 merge sort。
Recurrence Relation
演算法很重要的一個環節就是執行時間，接下來介紹如何分析執行時間。
・Unrolling the recurrence（recursion tree）：先展開問題找出規律，證明完成之後再將結果加起來即可。
・Substituting a guess：先預想一個答案，再用數學歸納法證明猜想正確。
Counting Inversions
Counting Inversions 是 merge sort 題型的延伸，可以用來計算兩個序列的相似度，用來定義兩者之間程度不同的情況便稱為 inversion。
以上圖為例，可以先固定其中一個序列，再與另外一個序列配對，看看有多少個交錯（crossing），就是 inversion 的程度。由於 base rank 已經排序好了，所以我們只要計算要比較的 rank 從該 element 往後算有多少個 inversion，就可以知道交錯的程度，這種計算方法的時間複雜度為 Θ(n2)，但如果應用前面學到的 merge sort，就可以將時間降到 O(n log n)。
如前所述，分治法最困難的地方就是如何有效率的 combine，只要能在線性時間之內完成 combine，就可以保證演算法的時間複雜度可以控制在 O(n log n) 中。實現的概念為當每個小部分在處理 inversion 時順便排序，combine 執行兩部分 inversion 比較時，由於已經排序，就只要比較陣列中的部分元素即可。
Closest Pair of Points
這也是很常遇到的問題，主要是探討如何在許多平面的點中，找到直線距離（Euclidean distance）最近的兩個點。
這個問題如果直接計算平面上每兩個點之間的距離找出最小值，所需的時間複雜度為 Θ(n2)，因此在此我們一樣要試著使用分治法，讓時間複雜度降到 O(n log n)。
這個問題可以先簡化成一維空間來思考。如果今天所有的點都在同一條軸上，想知道兩點之間最近的距離，可以先將所有的點由小排到大，此時距離每個點最近的點一定會在其右側或左側，其他的點就不用考慮。在這個基礎上，再將問題延伸到二維空間，我們先假設所有點的 X 座標都不同，將平面上的點分別切成左右兩邊（數量皆為 n/2），此時有可能產生最近距離兩點的地方為：
・左右兩邊的兩個點（兩個點都在同一區）
・橫跨左右兩邊的兩個點（兩個點在不同區）只要分別計算出這三個條件兩點之間的長度，找出最佳解即可。
這個問題的困難點一樣是 combine 時的處理方式，由於我們先將平面分成左右兩邊，假設左側最右邊的點的 X 座標為 X*，切分線 L 的方程式則為 X = X*，接著先找出左右兩側兩點間最短的距離，只要在離切分線左右兩側最短距離內，找出是否有比同區內兩點距離還小的兩個點即可。
為了限縮比較時間，我們可以先將落在比較區塊內的點以 Y 軸為基礎做排序，假設以高排到低，此時只要往下比較 15 個點，就可以完成最兩個區塊最短距離的計算。相關推論如下：
・假設比較區塊的距離為 δ，先將左右兩側的區塊再分割成 δ/2，因此每個方塊都面積都是 δ/2 * δ/2，我們要證明兩件事：
・每個方塊裡面至多只會有一個點存在
・兩個落在區塊內的點 S 與 S’，其距離不會超過十五個方塊第一個推論可使用反證法：
・假設 S 與 S’ 在同一方塊內，則兩者之間的距離必定小於 L 到兩點的距離，也就是兩個點會在同一側，如此便和上面找到的最短距離相悖，因此兩點必定在不同的方塊內，故得知每個方塊至多只會有一個點存在。第二個推論一樣使用反證法：
・假設兩點之間的最短距離超過十六個方塊，則距離會超過 3/2δ，已經大於 δ，不會是最小距離，故不需計算。
完成的 pseudocode 如下：
相關連結：
