甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
把规模为n的问题P(n)，分解为k个规模较小、互相独立、结构与原来问题结构相同的子问题，又进一步的分解每个子问题，直到某个阀值n0为止。递归地解这些子问题，再把子问题的解合并起来，得到原问题的解。
创新互联建站2013年至今，先为鄄城等服务建站，鄄城等地企业，进行企业商务咨询服务。为鄄城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
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,...,yk); //将各子问题的解合并为原问题的解
}
人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。
三个步骤组成：
划分步：把输入的问题实例划分为k个子问题。尽量使k个子问题的规模大致相同。在很多情况下，使k=2。也有k=1的划分，仍把问题划分成两部分，取其中的一部分，而丢弃另一部分，如二叉检索问题用分治法处理 。
治理步：当问题的规模大于某个预定义的阀值n0时，治理步由k个递归调用组成。
阀值n0的选取：阀值可为任何正常数，大小与算法的性能有关。取决于算法中的adhoc对阀值n0的敏感程度，以及merge的处理情况。
组合步：把子问题的解组合起来，对分治算法的实际性能至关重要 。算法的有效性很大程度上依赖于组合步的实现！
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
给定数组a[0:n-1]，试设计一个算法，在最坏情况下用┌ 3n/2-2 ┐次比较找出a[0:n-1]中元素的最大值和最小值。
算法思想
复杂度分析：
把问题划分为左右两种的情况，需要分别递归求解,时间复杂度可如下计算：
有递推公式为：
- T(n)= 1 n=l
- T(n)=2T(n/2)+l n>l
所以，分治算法的时间复杂度是n+[logn]-2,当n为奇数时，logn取上线，当n为偶数时,logn取下线。
#include
int a[100];
void maxcmax(int i,int j,int &max,int &cmax){
int lmax,lcmax,rmax,rcmax;
int mid;
if(i==j){
max=a[i];
cmax=a[i];
}
else if(i==j-1){
if(a[i]rmax){
if(lcmax>rmax){
max=lmax;
cmax=lcmax;
}else{
max=lmax;
cmax=rmax;
}
}else{
if(rcmax>lmax){
if(rcmax==rcmax){
max=lmax;
cmax=lcmax;
}else{
max=lmax;
cmax=rmax;
}
}else{
max=rmax;
cmax=lmax;
}
}
}
}