资源描述：
《第2章 递归与分治策略课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析>递归与分治第二章递归与分治(DividandConquer)2.2基本思想Divide-and-Conquer(P)if(
2、P
3、<=n0)Adhoc(P);直接求解问题pdividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);将p1,p2,…pk的解y1,y2,…yk合并成p的解问题的规模阀值算法一般模式将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的
4、解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止.在分治法中,子问题的解法通常与原问题相同,自然导致递归过程.应用当中,通常将问题分解为k个(k=2)大小相等的子问题.1算法设计与分析>递归与分治设问题P(n)分解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:T(n)=算法的时间复杂性Divide-and-Conquer(P)if(
5、P
6、<=n0)Adhoc(P);dividePintosmallersubinstancesP1,P2
7、,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换,棋盘覆盖,排序,选择等.O(1)2算法设计与分析2.3二分搜索技术已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.functionsearch(c){i:=1;1whileA[i]8、+2)mifA[i]=cthensearch:=i;elsesearch:=0;1+1}算法1-1:顺序查找例题1-1最好情况Tmin(m)=4,最坏情况Tmax(m)=3+5m,Tmin(m)=O(1)Tmax(m)=O(m)3算法设计与分析2.3二分搜索技术算法1-2:二分查找例题1-1最坏情况Tmax(m)=O(logm)functionb-search(c){L:=1;U:=m;found:=false;whilenotfoundandU>=Ldo3(logm+1){i:=(L+U)div2;3(logm+1)ifc=A[i]logm+1thenfound:=trueelsei
9、fc>A[i]logm+1thenL:=i+1elseU:=i-12(logm+1)}iffoundthenb-search:=1elseb-search:=0}4寻找最大与最小元素从无序的数组a[0:n-1]中寻找最大与最小元素方法一：找最大元素：n-1次比较找最小元素：n-2次比较总计：2n-3次比较方法二（分治法）左右两部分分别求max1，min1和max2，min2合成：fmax=max(max1，max2)fmin=min(min1，min2)5递归方程0n=1T(n)=1n=2T(└n/2┘)+T(┌n/2┐)+2n>2T(n)=┌3n/2–2┐比较次数优于方法一。寻找最大
10、与最小元素6算法设计与分析>递归与分治通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。这个假定仅在硬件能对整数直接表示和处理时才合理。然而，在处理很大整数时，硬件无法直接表示和处理。而用浮点数来表示则只能近似值，计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，必须用软件方法来实现大整数的算术运算。如何设计两个大整数的乘法运算的有效的算法？要求：大整数超出longint表示范围，而浮点表示不精确。假设：乘法时间远大于加减法、移位运算将两个一位数的乘法或加法
11、看作一步运算，那么，两个N位数X*Y相乘，需要O(N2)时间2.4大整数的乘法算法问题:设X,Y是两个n位二进制数,求XY.7算法设计与分析>递归与分治分治算法思路:若两个1位数相乘或相加看作1步运算,按传统乘法需O(n2)次运算.将每个n(n=2K)位的二进制整数分为2段,每段的长为n/2位计算XY须3次n/2位整数的乘法,6次加.减和2次移位X=A2n/2+By=C2n/2+D。XY＝(A2n/2+B)(C2n/2+D)＝AC2n+(AD+
