YI時間｜外刊｜MM-DFW｜機器學習系列
點擊上方藍字，關注給你寫干貨的松子茶

分治策略是通用算法設計技術之一，很多有效的算法是它的特殊實現,顧名思義就是分而治之。一個問題能夠用分治法求解的要素是

• 問題能夠按照某種方式分解成若干個規模較小、相互獨立且與原問題類型相同的子問題；

• 子問題足夠小時可以直接求解；

• 能夠將子問題的解組合成原問題的解。

由于分治法要求分解成同類子問題，并允許不斷分解，使問題規模逐步減小，最終可用已知的方法求解足夠小的問題，因此，分治法求解很自然導致一個遞歸算法。

通過二分檢索算法BinarySearch(T, l, r, x)和二分歸并排序算法MergeSort(A,p,r)?? 展示分治策略的特點：

• 將原問題歸約為規模小的子問題，子問題與原問題具有相同的性質.

• 子問題規模足夠小時可直接求解.

• 算法可以遞歸也可以迭代實現.

• 算法的分析方法：遞推方程.

分治策略的算法分析工具：遞推方程

求解方法

• 第一類方程：迭代法、換元法、遞歸樹、嘗試法

• 第二類方程：迭代法、遞歸樹、主定理

3 ?改進分治策略的兩種途徑：

• 通過代數變換減少子問題個數，如：位乘問題、矩陣乘法。

• 利用預處理減少遞歸內部操作，即：算法中的處理盡可能提到遞歸外面作為預處理。如：平面點對問題。

歡迎評論哦，糾錯評論建議均可

-THE END-

版權聲明：以上內容為松子茶公眾號原創作品，版權歸屬作者所有。未經作者授權，嚴禁轉載或鏡像，否則將依法追究相關行為主體的法律責任。歡迎各位朋友轉發朋友圈分享。

總結

以上是生活随笔為你收集整理的算法设计与分析_算法设计与分析（第2版）第2章分治策略回顾的全部內容，希望文章能夠幫你解決所遇到的問題。

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