分治法 在计算机科学中分治法英語Divide and conquer是建基於多項分支遞歸的一种很重要的算法範式字面上的解释是分而治之就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并 这个技巧是很多高效算法的基础如排序算法归并排序快速排序傅立叶变换快速傅立叶变换 另一方面理解及設計分治法算法的能力需要一定時間去掌握正如以歸納法去證明一個理論為了使遞歸能夠推行很多時候需要用一個較為概括或複雜的問題去取代原有問題而且並沒有一個系統性的方法去適當地概括問題 分治法這個名稱有時亦會用於將問題簡化為只有一個細問題的算法例如用於在已排序的列中尋找其中一項的折半搜索算法或是在數值分析中類似的勘根算法這些算法比一般的分治算法更能有效地執行其中假如算法使用尾部遞歸的話便能轉換成簡單的迴圈但在這廣義之下所有使用遞歸或迴圈的算法均被視作分治算法因此有些作者考慮分治法這個名稱應只用於每個有最少兩個子問題的算法而只有一個子問題的曾被建議使用減治法這個名稱 分治算法通常以數學歸納法來驗證而它的計算成本則多數以解遞迴關係式來判定