分治法的基本思想
分治法的基本思想是将一个规模为\(n\)的问题分解为\(k\)个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解。
1.分治法划分问题的方法是递归划分，且子问题的规模最好是相等的，即将一个问题分为大小相等的\(k\)个子问题，多出情况下可以取\(k=2\)
2.对子问题进行递归求解，在问题规模最够小的时候可以使用停止递归
3.合并子问题得到原问题解，合并的过程是整个算法的精髓(@>_<@)
一般算法设计模式
用\(|P|\)表示问题\(P\)的规模，\(n_0\)表示一个阈值，当\(|P|\)小于等于\(n_0\)时，问题可以很容易求出，不必再分解；当\(|P|\)大于\(n_0\)时，问题分解为\(k\)个子问题，分别求出之后再将其合并。所以可得出分治法的一般算法设计模式如下：
divide-and-conquer(p) {
if (|p| <= n0)
adhoc(P);
divide P into smaller subinstances P1,P2,···,Pk;
for (i=1; i <= k; i++)
yi = divide-and-conquer(Pi);
return merge(y1, y2, ···, yk);
}
下面分析上述算法时间复杂性，设原问题规模\(|P|=n\)，子问题规模相等且为\(n/m\)；adhoc解规模为\(n_0\)的问题耗费1单位时间；将原问题分解为\(k\)个子问题，并将它们的解合并为原问题的解耗费\(f(n)\)单位时间，则
分治典例
1.二分搜索算法
二分搜索算法的基本思想是，将\(n\)个元素分成个数大致相同的两半，取\(a[n/2]与x\)做比较。如果\(x=a[n/2]\)，则找到\(x\)，算法终止；如果\(x<a[n/2]\)，则只在数组\(a\)的左半部继续搜索\(x\)；如果\(x>a[n/2]\)，则只在数组\(a\)的右半部继续搜索\(x\)。具体算法如下：
template<class Type>
int BinarySearch(Type a[], const Type& x, int n) {
//找到x时返回其在数组中的下标，否则返回-1
int left = 0; int right = n-1;
while (left <= right){
int middle = (left+right)/2;
if (x == a[middle])
return middle;
if (x > a[middle])
left = middle + 1;
else
right = middle - 1;
}
return-1;
}
在该算法中，原问题被分为\(k=2\)个规模相同且与原问题相同的子问题。在最坏的情况下，while循环被执行了\(O(long_2^n)\)次，循环内运行所需时间为\(O(1)\)，所以该算法在最坏情况下的时间复杂性为\(O(long_2^n)\)。
2.快速排序
快速排序算法的基本思想是将待排序数组\(a[p:r]\)，分为\(a[p:q-1]\)、\(a[q]\)、\(a[q+1:r]\)三个部分。其中，\(a[p:q-1]\)中任意元素小于等于\(a[q]\)；\(a[q+1:r]\)中任意元素大于\(a[q]\)。通过递归调用快速排序算法，分别对\(a[p:q-1]\)和\(a[q+1:r]\)进行排序。最后将结果合并，如果排序就地进行，则算法结束之后\(a[p:r]\)就已排好序。具体算法如下：
template<class Type>
void QuickSort (Type a[], int p, int r){
if (p < r){
int q = Partition(a, p, r);//以a[q]为基准排序
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
Partition()如下：
template<class Type>
int Partition (Type a[], int p, int r){
int i = p, j = r+1;
Type x = a[p];
while (true){
while (a[++i] < x && i < r) ;
while (a[--j] > x) ;
if (i >= j)
break;
Swap(a[i], a[j]);
}
a[p] = a[j];
a[j] = x;
return j;//返回划分节点
}
该算法将原问题分为了\(k=2\)个与原问题相同的解，但是问题规模和所选定的基准有关。对于\(n\)个输入，Partition算法的计算时间为\(O(n)\)。在最坏情况下，划分的两个数组一个有\(1\)个元素，另一个有\(n-1\)个元素，则
解此递归方程可得\(T(n)=O(n^2)\)。
在最好情况下，每次划分都使得两边的元素数量相等，此时有
解此递归方程可得\(T(n)=O(nlog_2^n)\)。
可以从数组中随机抽取一个元素作为基准，这样可以期望划分是较对称的。