- 基本思想
- 適用情況
- 基本步驟
- 程序設計
- 思維過程
- 一般的算法設計模式
- 復雜度
- 經典運用
# 基本思想：
-
字面上的解釋是“分而治之”惭嚣，就是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題(
反復分解直到問題小到可直接求解為止)遵湖，使這些子問題相互獨立可分別求解，再將k個子問題的解合并成原問題的解晚吞。- 這些子問題
相互獨立且與原問題性質相同(規(guī)模一般也相同)延旧。只要求出子問題的解，合并就可得到原問題的解槽地。
- 這些子問題
在分治法中迁沫，子問題的解法通常與原問題相同芦瘾。這自然導致
遞歸過程。
分治與遞歸像一對孿生兄弟集畅，經常同時應用在算法設計之中近弟，并由此產生許多高效算法。
# 適用情況
分治法能解決的問題一般具有以下4個特征：
（1）當問題的規(guī)哪嫡縮小到一定的程度就可以容易地解決藐吮。
（2）問題可以分解為若干個規(guī)模較小的問題溺拱，即該問題具有最優(yōu)子結構性質逃贝。
（3）利用該問題分解出的子問題的解可以合并為該問題的解（關鍵）；
（4）各個子問題是相互獨立的迫摔，即子問題之間不包含公共的子問題沐扳。
- 第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規(guī)模的增加而增加句占；
-
第二條特征是應用分治法的前提,它也是大多數問題可以滿足的沪摄，此特征反映了遞歸思想的應用； 第三條特征是關鍵纱烘，能否利用分治法完全取決于問題是否具有第三條特征杨拐，如果具備了第一條和第二條特征，而不具備第三條特征擂啥，則可以考慮用貪心法或動態(tài)規(guī)劃法哄陶。-
第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作哺壶，重復地解公共的子問題屋吨，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較好山宾。
這個思想是很多高效算法的基礎至扰，在各種排序方法中，如：歸并排序资锰、堆排序敢课、快速排序等，都存在有分治的思想绷杜。還有傅立葉變換(快速傅立葉變換)等
# 基本步驟：
- 分解翎猛，將要解決的問題劃分成若干個規(guī)模較小的同類問題
- 求解，當子問題劃分得足夠小時接剩，用較簡單的方法解決
-
合并切厘，按原問題的要求，將子問題的解逐層合并構成原問題的解
分治
要點：
- 分幾個懊缺？子問題規(guī)模多大疫稿？ 最好使子問題的規(guī)模大致相同培他。即將一個問題分成大小相等的 k 個子問題的處理方法是行之有效的。
- 子問題如何求解?
- 合并原問題的解?
- 分析時間復雜性
# 程序設計
## 依據分治法設計程序時的思維過程
實際上就是類似于數學歸納法遗座，找到解決本問題的求解方程公式舀凛，然后根據方程公式設計遞歸程序。
- 一定是先找到最小問題規(guī)模時的求解方法
- 然后考慮隨著問題規(guī)模增大時的求解方法
- 找到求解的遞歸函數式后（各種規(guī)耐窘或因子）猛遍，設計遞歸程序即可。
分治的算法思想與遞歸往往是相伴而生的
## 一般的算法設計模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 將P分解為較小的子問題 P1 ,P2 ,…,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
6. T ← MERGE(y1,y2,…,yk) △ 合并子問題
7. return(T)
其中:
|P|表示問題P的規(guī)模号坡；
n0為一閾值懊烤，表示當問題P的規(guī)模不超過n0時，問題已容易直接解出宽堆，不必再繼續(xù)分解腌紧。
ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問題P畜隶。因此壁肋，當P的規(guī)模不超過n0時直接用算法ADHOC(P)求解。
算法MERGE(y1,y2,…,yk)是該分治法中的合并子算法籽慢，用于將P的子問題P1 ,P2 ,…,Pk的相應的解y1,y2,…,yk合并為P的解浸遗。
## 復雜度
一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設分解閥值n0=1箱亿，且adhoc解規(guī)模為1的問題耗費1個單位時間跛锌。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間极景，則有：
通過迭代法求得方程的解：
遞歸方程及其解只給出n等于m的方冪時T(n)的值察净，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度盼樟。通常假定T(n)是單調上升的氢卡，從而
當時，
# 經典運用：
- 二分查找
- 合并(歸并)排序
- 快速排序
- 最大子段和
- 最近對
- 凸包
- 漢諾塔
- 大數相乘問題
- 比賽日程安排
- 尋找假幣問題
- Strassen矩陣乘法
- 棋盤覆蓋
- 線性時間選擇
...
//示例代碼：二分查找
#include <stdio.h>
int bin_search(int A[], int n, int key)
{
int low = 0, high = 0, mid = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (A[mid] == key) { //查找成功晨缴，返回mid
return mid;
}
if (A[mid] < key) { //在后半序列中查找
low = mid + 1;
}
if (A[mid] > key) { //在前半序列中查找
high = mid - 1;
}
}
return -1; //查找失敗
}
int main(int argc, const char * argv[]) {
// insert code here...
int A[10] = {2, 3, 5, 7, 8, 10, 12, 15, 19, 21};
int i = 0, n = 0, addr = 0;
printf("The contents of the Array A[10] are\n");
for (i = 0; i < 10; i++) {
printf("%d ",A[i]); //顯示數組A中的內容
}
printf("\nPlease input a interger for search\n");
scanf("%d", &n); //輸入待查找得元素
addr = bin_search(A, 10, n); //折半查找译秦，返回該元素在數組中的下標
if (-1 != addr) {
printf("%d is at the %dth unit is array A\n", n, addr);
}else{
printf("There is no %d in array A\n", n); //查找失敗
}
getchar();
return 0;
}
