圖解！ACM 選手帶你玩轉分治演算法！
大家好呀，我是 Rocky0429。
在上一篇文章中我講了遞迴演算法：
ACM 選手帶你玩轉遞迴演算法！
遞迴是一種很重要的演算法，經常在一些高階的演算法中應用，比如今天我要講的分治演算法。
分治演算法同樣也是一種很重要的演算法，可能很多小婊貝們都聽說過分治演算法，但是沒有系統的瞭解過。
這篇文章，就讓我們來一探究竟。
什麼是分治？
學習分治，得先知道什麼是分治。
分治，表面意思就是“
分而治之
”，洋名兒叫
Divde & Conquer
。
正規點的說法是：
分治演算法就是將一個大的複雜的問題，拆分成多個相同或者相似的子問題，然後再把子問題拆成更小的子問題，然後再拆成更更小的問題 and so on
直至最後的子問題可以簡單求解，那最後問題的解即子問題解的合併。
白話點說就是：
將一個難題，拆成一些規模較小的相同的子問題，各個擊破，分而治之。
很多演算法用到了分治的思想，比如排序演算法中的快排和歸併排序，這些等我講到排序演算法的時候再來細聊。
由此可以看出，
分治演算法真真正正是一種處理問題的思想
，這個要區別於遞迴，
遞迴只是一種程式設計技巧
。
分治演算法的過程
分治演算法由“分”和“治”兩部分組成
，但是它主要包括
3 個過程
：
劃分（Divide）
求解（Conquer）
合併（Combine）
其中：
劃分（Divide）
：將原問題劃分為規模較小的子問題，子問題相互獨立，與原問題形式相同。
求解（Conquer）
：遞迴的求解劃分之後的子問題。
合併（Combine）
：這一步非必須。有些問題涉及合併子問題的解，將子問題的解合併成原問題的解。有的問題則不需要，只是求出子問題的解即可。
分治演算法的整個流程可以看下圖：
分治演算法適用情況
由分治演算法的過程可以看出分治演算法適用的情況，我的總結是 4 個詞：
規模大
可分解
各獨立
可合併
“規模大”和“可分解”針對原始問題。
即原問題要規模比較大，不易直接解決，但是問題分解成規模較小的相同子問題比較容易解決。
“各獨立”和“可合併”針對子問題。
即子問題之間求解是相關獨立互不影響，且子問題的解可以合併成原始問題的解。
這四個詞中最重要的是“各獨立”和“可合併”。
“各獨立”涉及到分治法的效率問題。
如果各個子問題是不獨立的，則分治法就需要重複的去解決一些重複的子問題，這樣多做了很多不必要的工作。
比如我們很熟悉的斐波那契數列，公式如下：
假設我們要求 f（5），分治法將其劃分為一個個的子問題：
由上圖可見，僅僅是求 f（5），僅僅是隻畫了 3 層，就已經出現了相同結果的重複計算（比如 f（3） 和 f（2））。
透過對子問題解的合併，最終的結果毋庸置疑，但是因為各個子問題的不獨立，造成了子問題的重複計算，從而分治法求解斐波那契的效率感人。。。
碰到這種情況，還是動態規劃比較合適。。。
“可合併”是涉及能否用分治的關鍵。
如果子問題的解可合併，那就能用分治法。
如果不可合併，單單只是“規模大”和“可分解”，分治就沒必要考慮，用貪心或者動態規劃才是正理。
設計分治演算法
透過之前的瞭解，其實可以很清楚的發現，
用分治演算法解決問題的核心，其實就是歸納一個求解的數學公式，然後根據公式設計遞迴程式
。
說白了就是
先找找拆分到最小規模問題時怎麼解，然後再瞅瞅隨著問題規模增大點問題怎麼解，最後就是找到遞迴函式，碼出遞迴程式碼即可
。
分治演算法例項
其實在這之前，我已經講過一個典型的分治演算法的應用：二分查詢。
可以說二分查詢是分治演算法中最常用的演算法：
ACM 選手帶你玩轉二分查詢！
二分查詢是在一個有序的陣列中進行查詢嗎，每次可以讓問題的規模減半。
它思路比較簡單：
選擇一個 mid 將陣列分為左右兩個集合。
判斷標誌 arr［mid］ 是否能與要查詢的目標值 target 相等，相等則直接返回。
若小於 arr［mid］，則在左半區間繼續查詢。
如大於 arr［mid］，則在右半區繼續查詢。
遞迴上面的步驟。
def BinarySearch（arr， low， high， target）：
if low <= high：
mid = （low + high） / 2
if arr［mid］ == target：
return mid
elif arr［mid］ < target：
return BinarySearch（arr， low， mid - 1， target）
else：
return BinarySearch（arr， mid + 1， high， target）
else：
# 沒有找到
return -1
分治演算法
到這就講完辣，原理很簡單，小婊貝們看會了麼？
原理搞懂只是邁出學會分治演算法的第一步，
想要靈活的使用卻不是一件容易的事兒
，更多的還是要在實戰中領悟，在實戰中加深對分治演算法的理解。
大家只要認真去搞，就一定能掌握分治演算法。
我是 @Rocky0429 ，我們下次見。
推薦閱讀：
保姆級教學！徹底學會時間複雜度和空間複雜度
蛋蛋慘遭陣列滑鐵盧，面試官建議回村養豬。
連結串列，畫幾下就整明白了！
呔！“棧”住，佇列！
ACM 選手帶你玩轉雜湊表！
ACM 選手帶你玩轉 KMP 演算法！
