分、治、合三步:切成小問題、各自解決、再合併答案。合併 / 快速排序都是這派。
分 divide —— 把問題切成幾個更小的同類子問題(通常對半切)。
治 conquer —— 每個子問題各自遞迴解;小到不能再切就直接給答案(base case)。
合 combine —— 把子答案合併成原問題的答案。這一步往往是關鍵,也是難點。
跟一般遞迴的差別 —— 分治的子問題通常大小相近、彼此獨立,重點在「怎麼合」。
對半切 → 只要 log n 層 —— 每切一次規模砍半,樹的深度是 log n。
每層總工作量常是 O(n) —— 例如合併排序每層合併都要掃過所有元素。
log n 層 × 每層 O(n) = O(n log n) —— 這就是合併 / 快速排序速度的來源。
若「合」只要 O(1)、每次只遞迴一半 —— 例如二分搜尋 → 只有 log n 層、每層 O(1) = O(log n)。
T(n) = a·T(n/b) + 合併成本 —— 切成 a 塊、每塊 1/b 大。二分搜尋 a=1、b=2、合 O(1) → O(log n);合併排序 a=2、b=2、合 O(n) → O(n log n)。合併排序 —— 切一半、各自排、合併(合是重點)。
快速排序 —— 選基準分兩堆、各自快排(分是重點)。
二分搜尋 —— 每次只遞迴一半(退化的分治,不用合)。
還有 —— 快速冪、最大子陣列、最近點對、大數乘法(Karatsuba)、FFT…(範例區有)。
想數一大盤披薩幾片?分兩半各請一人數,再把兩人的數字加起來(合)。
總經理問各部門、部門問各組,各組回報數字再一層層往上加總。
每個投開票所各自數票,再把各所的票數合起來就是總票數。
用分治找 [3, 8, 2, 5] 的最大值。先一路分到剩單一元素(紫色),那就是 base case(琥珀);再由下往上合,每一步取兩半的較大者(綠色數字)。按「下一步」走一遍。
從分治找最大 / 求和,到合併排序、二分搜尋、快速冪、最大子陣列、逆序對、Karatsuba,最後給通用模板。
❌ 忘了「合」 —— 分治的難點常在合併那步,不是切。切完不會自己合起來。
❌ 子問題沒變小 / base case 錯 —— 跟遞迴一樣會停不下來。
❌ 以為分治一定比較快 —— 找最大值分治還是 O(n)。分治快是因為「砍半 + 合併便宜」,不是因為它叫分治。
❌ 過度切割小資料 —— 子問題太小時遞迴開銷反而慢,實務會設門檻改用簡單方法(如插入排序)。
[3, 8, 2, 5] 用分治找最大值,畫出「分」的樹,再寫出「合」時每一步 max 的結果。(用視覺化對)O(log n)、合併排序是 O(n log n),同樣「對半分治」,為什麼差一個 n?把答案打到對話裡,我幫你對。