? ? ?一、概念： 在計算機科學中，分治法是建基于多項分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，直到最后子問題可以寄簡單的直接求解，原問題的解即子問題的解的合并。

這個技巧是很多高校算法的基礎，如排序算法（快速排序、歸并排序）、傅立葉轉換（快速傅立葉變換） 思路： 1.分解：把原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。 2. 解決：若子問題規模較小且易于解決時，則直接解。否則，遞歸地解決各子問題。 3.合并：講各子問題的解合并為原問題的解。 分治算法是按照下列方案來工作的：
1）將問題的實例劃分為幾個較小的實例，最好具有相等的規模（事實上，一般來說就是這樣來分的，而且分為2個實例的居多，注意是遞歸的分！！！）

2）對這些較小的實例求解（一般使用遞歸的方法，但在問題規模足夠小的時候也可以采用采用另一個算法（停止遞歸））

3）如果有必要的話，合并這些較小問題的解，以得到原始問題的解（事實上，一個分治算法的精華就在于合并解的過程）

不要忽視這三句話！！！它是許多分治算法經驗的總結，有助于在分析問題中考慮如何去使用分治算法，提請注意括號里我的注釋！！！

形象的表示一下，截張圖： 參照：http://www.cnblogs.com/kkgreen/archive/2011/06/10/2077923.html 總結：

1）分治的思想：一般遞歸來實現，劃分子問題，合并子問題的解。

2）主定理，要很熟悉，常見的遞推式應該一眼判斷其復雜度。

3）合并排序，快速排序，折半查找，二叉遍歷樹相關特性，這些都是數據結構的經典內容，之前也都寫過了，代碼參見前面的相關文章。

這里再次復習，從不同的視角來看它們都是如何用用到了分治的策略。這些內容應當非常熟練。

轉載于:https://www.cnblogs.com/cphmvp/p/3892184.html

總結

以上是生活随笔為你收集整理的005-算法-分治法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。