第七章分治算法所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解
当我们将问题分解成两个较小问题求解时的分治方法称之为二分法
分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相似
找出各部分的解，然后把各部分的解组合成整个问题的解
1、解决算法实现的同时，需要估算算法实现所需时间
分治算法时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量决定）合并所有子问题所需的工作量
2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法
3、分治的具体过程：{｛开始｝if①问题不可分②返回问题解else{③从原问题中划出含一半运算对象的子问题1；④递归调用分治法过程，求出解1；⑤从原问题中划出含另一半运算对象的子问题2；⑥递归调用分治法过程，求出解2；⑦将解1、解2组合成整个问题的解；}}//结束【例1】快速排序(递归算法)voidqsort(intl,intr){inti,j,mid,p;i=l;j=r;mid=a[(l+r)/2];//将当前序列在中间位置的数定义为分隔数do{while(a[i]mid){j--;}//在右半部分寻找比中间数小的数if(i>m;//输入要查找的数jc(x,y);//递归过程cout
