勵志

勵志人生知識庫

分冶

分冶,中文名為分治算法,是一種在計算機科學中常用的算法設計策略。其基本思路是將一個難以直接解決的大問題,分割成一些規模較小的相同問題,以便於各個擊破求解。分治法的適用情況包括:

問題的規模縮小到一定程度就可以解決

該問題可以被分解為幾個小的規模的相同問題,即該問題具有最優子結構

該問題分解的子問題可以合併為該問題的解

該問題分解的子問題之間是互相獨立的

分治算法的經典問題包括二分搜尋大整數乘法Strassen矩陣乘法棋盤覆蓋合併排序快速排序線性時間選擇最接近點問題循環賽日程表漢諾塔等。設計分治算法的思維過程實際上類似於數學歸納法,根據方程公式設計遞歸程式,找到最小問題規模時的求解辦法,考慮隨著問題規模增大時的求解方法,找到遞歸函式式,設計遞歸程式。