分治算法

1.定義

將原問題劃分成n個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些子問題，然后再合并其結果，就得到原問題的解。

2.分治策略

“分而治之”，大問題能夠拆成相似的小問題，記住這些小問題需要具有相似性。而后將小問題的每個解合成為大問題的解。所以說大問題如何拆，小問題如何合并才是這個算法最主要的一個思想。實際上很多算法如貪心算法，動態規劃等等都是要求把大問題拆成小問題。而分治算法的重要一點就是要適用于能夠重新把小問題的解合并為大問題的解。

3.使用分治算法的前提條件

• 原問題與分解成的小問題具有相同的模式；
• 原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別；
• 具有分解終止條件，也就是說，當問題足夠小時，可以直接求解；
• 可以將子問題合并成原問題，而這個合并操作的復雜度不能太高，否則就起不到減小算法總體復雜度的效果了

4.每一次遞歸都會涉及三個操作

• 分解：將原問題分解成一系列子問題；
• 解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；
• 合并：將子問題的結果合并成原問題。

5.分治法適用條件

1. 　該問題的規模縮小到一定程度就可以很容易解決；
2. 　該問題可以分解為若干個規模較小的相同問題，這里注意是最優子結構性質；
3. 　利用該問題分解出的子問題的解可以合并為該問題的解；
4. 　該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共子問題。

說明：

• 對于很多算法而言，第一條往往是必要的，因為數據量一旦大起來，問題往往復雜度上升的特別快。這里就需要將這個大問題分解為小問題。小問題處理起來更加方便。
• 第二、三條的才是分治思想的核心，因為很多時候我們會采用遞歸的方式進行解決，所以在大問題分解為小問題的時候需要保證小問題之間的相同性。
• 單單分解為小問題之后還不能算完成，必須要能夠將小問題的解合并為這個問題的最終解才能算真正用到了分治的思想。
• 最后一條也是最關鍵的，各個子問題之間必須要保證獨立性，即不互相影響。如果相互之間有影響，這時候我們采用的是動態規劃就更加好一點。

6.案例

在各種排序方法中，如歸并排序、堆排序、快速排序等，都存在有分治的思想。