分冶,中文名為分治算法,是一種在計算機科學中常用的算法設計策略。其基本思路是將一個難以直接解決的大問題,分割成一些規模較小的相同問題,以便於各個擊破求解。分治法的適用情況包括:
問題的規模縮小到一定程度就可以解決
該問題可以被分解為幾個小的規模的相同問題,即該問題具有最優子結構
該問題分解的子問題可以合併為該問題的解
該問題分解的子問題之間是互相獨立的
分治算法的經典問題包括二分搜尋、大整數乘法、Strassen矩陣乘法、棋盤覆蓋、合併排序、快速排序、線性時間選擇、最接近點問題、循環賽日程表、漢諾塔等。設計分治算法的思維過程實際上類似於數學歸納法,根據方程公式設計遞歸程式,找到最小問題規模時的求解辦法,考慮隨著問題規模增大時的求解方法,找到遞歸函式式,設計遞歸程式。