分治法的基本思想_五大算法之一，分治算法

1.分治算法的基本思想

将一個規模為N的問題，分解成K個規模較小的子問題，這些子問題互相獨立且月原問題性質相同。

求解出子問題的解，合并得到原問題的解。

2.分治算法特征分析

分治法能解決的問題一般具有以下幾個特征：

1) 該問題的規模縮小到一定程度就可以容易的解決；

2) 該問題可以分解為若幹個規模較小的相同問題，即該問題具有最優子結構性質；

3) 利用該問題分解出子問題的解，可以合并為該問題的解；

4) 該問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子子問題；

分治算法大多采用遞歸實作，第二條特征就反應了遞歸思想的引用。

如果滿足了第一條特征和第二條特征，不滿足第三條特征，可以考慮用貪心法或動态規劃法。

如果不滿足第四條特征，也可以用分治法，但是要做很多不必要的工作，重複的解公共的子問題，是以一般用動态規劃法比較好。

3.實際應用場景

二分查找，階乘計算，歸并排序，堆排序、快速排序、傅裡葉變換都用了分治法的思想。

4.依據分治法設計程式的思維過程

實際上類似數學歸納法，找到解決本問題的求解方程公式，然後根據方程公式設計遞歸程式。

1) 一定是先找到最小問題規模時的求解方法

2) 然後考慮随着問題規模增大時的求解方法

3) 找到求解的遞歸函數後，設計遞歸程式即可。

關鍵字:網際網路 大資料 算法與資料挖掘

注:圖檔是北京某羽毛球館