算法设计与分析耿国华第二章_第1页
算法设计与分析耿国华第二章_第2页
算法设计与分析耿国华第二章_第3页
算法设计与分析耿国华第二章_第4页
算法设计与分析耿国华第二章_第5页
已阅读5页,还剩114页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第二章递归与分治策略算法设计与分析算法设计与分析耿国华本章内容2.1递归的概念2.2具有递归特性的问题2.3递归过程的设计与设计2.4递归算法分析2.4.1替换法2.4.2递归树法2.4.3主方法2.5分治法的基本思想2.6分治法的适用条件2.7分治法的基本步骤2.8分治法典型示例2.8.1n个数中求出最大/最小值2.8.2快速排序2.8.3大整数乘法2.8.4折半查找2.8.5

矩阵乘法小结

Chapter22递归与分治策略当计算机求解的问题规模较大,直接解决困难甚至根本没办法直接求解时,往往会考虑能否将该问题分割成几个具有同等性质的子问题,将问题规模减小后完成求解过程。例如,对于n个数的排序问题,当n为1时,不需要进行任何比较运算,当n=2时,仅需进行一次比较运算即可,当n为3时,需要进行两次比较,依此类推。当n比较大时,这样的排序方式就比较难以处理,程序运行的效率会很低。诸如此类的大规模问题,往往会考虑能否将该问题分割成几个具有同等性质的子问题,将问题规模减小后完成求解过程。

Chapter22递归与分治策略基于这种指导思想,引出了分治法。由于分治法产生的子问题往往是原问题的较小模式,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易求解。由于分治后的子问题与原问题的类型一致,因此,在分治法中经常使用递归技术求解问题,递归与分治两者之间是相辅相成的。

Chapter22.1递归概念

在定义自身的同时,出现对自身的直接或间接调用(自己调用自己)。一个直接或间接调用自己的算法称为递归算法。

Chapter22.1递归概念递归算法的特点(1)描述简捷;(2)结构清晰;(3)算法的正确性比较容易证明。Chapter22.1递归概念递归转为非递归的原因(1)递归的执行效率低;(2)空间消耗多;(3)软、硬件环境条件限制;

Chapter22.1递归概念写递归注意问题(1)算法中的过程或函数对自身进行调用;(2)递归控制条件;有一个明确的递归结束条件,即递归出口;(3)非递归的初始值的定义。Chapter22.1递归概念递归设计方法(1)寻找分解方法;(2)设计递归出口(寻找所分解的问题的出口)。Chapter22.1递归概念递归算法的执行过程中包括两个执行阶段(1)自上而下的递归进层阶段(递推阶段)(2)自下而上的出层阶段(回归阶段)Chapter22.2具有递归特性的问题(1)递归定义的数学函数例2-1递归定义的Ackerman函数:Chapter22.2具有递归特性的问题

上述Ackerman函数的算法描述如下:

procedureintack(m,n) ifm=0then returnn+1; elseifn==0then returnack(m-1,1); elsereturnack(m-1,ack(m,n-1)); endif endackChapter22.2具有递归特性的问题例2-2:递归定义的斐波那契(Fibonacci)序列。 无穷数列1,1,2,3,5,8,13,21,34,……可定义为斐波那契数列。递归形式为Chapter22.2具有递归特性的问题

根据函数的递归定义,可以直接设计算法2.2求解斐波那契过程F(n)如下,

procedureF(n) ifn≤1then return1 else returnF(n-1)+F(n-2)endif endFChapter22.2具有递归特性的问题Chapter2图2-1斐波那契算法的递归结构(n=6)2.2具有递归特性的问题(2)递归定义的数据结构

在数据结构中,如广义表、二叉树、树等结构其本身均具有固有的递归特性,可以自然地采用递归法进行处理。(3)递归求解方法

许多问题的求解过程可以用递归分解的方法描述,例如:计算两非负整数最大公约数的欧几里得算法和著名的汉诺塔问题(Hanoi)问题。

Chapter22.2具有递归特性的问题例2-3:欧几里得(Euclid)算法。

已知两个非负整数a和b,且a>b≥0,求这两个数的最大公因数。 辗转相除法:若b=0,则a和b的最大公因数等于a;若b>0,则a和b的最大公因数等于b和用b除a的余数的最大公因数。当a=22,b=8时,递归结构如图2-2所示。Chapter22.2具有递归特性的问题Chapter2根据辗转相除法的递归定义算法2.2用递归解决两个数的最大公因数procedureGCD(a,b)

//约定a>bifb=0thenreturn

aelsereturn

GCD(b,amodb)endifendGCD图2-2

当a=22,b=8时,辗转相除法递归结构(n=6)2.2具有递归特性的问题例2.4汉诺塔(Hanoi)问题。

现在有三根柱子,标号为X,Y,Z,X柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,现在把所有盘子一个一个移动到柱子Z上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要多少次移动,设移动次数为H(n)。

Chapter22.2具有递归特性的问题例2.4汉诺塔(Hanoi)问题。

分析:当n很大时这个问题不好解决,我们可以使用递归技术来解决该问题 当n=1时,将编号为1的圆盘从X柱子直接移到柱子Z上。 当n>1时,需要利用柱子Y作为辅助柱子,设法将n-1个较小的盘子按规则移到柱子Y中,然后将编号为n的盘子从X柱子移到Z柱子,最后将n-1个较小的盘子移到Z柱子中。Chapter22.2具有递归特性的问题例2.4汉诺塔(Hanoi)问题。

算法2.4用递归解决规模为n的Hanoi塔问题

VoidHANOI(n,X,Y,Z) { ifn=1 MOVE(X,1,Z) else{ HANOI(n-1,X,Z,Y) MOVE(X,n,Z) HANOI(n-1,Y,X,Z) } }Chapter22.2具有递归特性的问题

下面给出三个盘子搬动时HANOI(3,A,B,C)的递归调用过程,如图2-3所示HANOI(3,A,B,C)HANOI(2,A,C,B):HANOI(1,A,B,C) MOVE(A->C)1号搬到CMOVE(A->B)2号搬到BHANOI(1,C,A,B) MOVE(C->B)1号搬回到BMOVE(A->C)3号搬到CHANOI(2,B,A,C):HANOI(1,B,C,A) MOVE(B->A)1号搬到AMOVE(B->C)2号搬到CHANOI(1,A,B,C) MOVE(A->C)1号搬到CChapter22.2具有递归特性的问题Chapter2图2-3汉诺塔的执行过程(n=3)2.3递归过程的设计与实现Chapter2

在算法的递归调用过程中,进行递归进层(i→i+1层)系统需要做三件事:⑴保留本层参数与返回地址;⑵为被调用函数的局部变量分配存储区,给下层参数赋值;⑶将程序转移到被调函数的入口。而从被调用函数返回调用函数之前,递归退层(i←i+1层)系统也应完成三件工作:⑴保存被调函数的计算结果;⑵释放被调函数的数据区,恢复上层参数;⑶依照被调函数保存的返回地址,将控制转移回调用函数。2.3递归过程的设计与实现Chapter2

当递归函数调用时,应按照“后调用先返回”的原则处理调用过程,因此上述函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中,每当调用一个函数时,就为它在栈顶分配一个存储区,而每当从一个函数退出时,就释放它的存储区。显然,当前正在运行的函数的数据区必在栈顶。2.3递归过程的设计与实现Chapter2例2.5n阶乘的递归算法和递归调用过程(0为最小规模)

((n-1)比n的规模更小)其递归算法如下:intf(intn)/*设n>=0*/{ if(n==0)return(1); elsereturn(n*f(n-1));}2.3递归过程的设计与实现Chapter2图2-4f(3)递归调用示意图2.3递归过程的设计与实现Chapter2递归进层3件事:保存本层参数、返回地址分配局部数据空间,传递参数转第一条指令递归退层3件事:恢复上层传递结果转断点执行2.3递归过程的设计与实现Chapter2 f(3)3x2

f(2)2x1自上而下自下而上递

归进层阶段f(1)1x1返回阶段 f(0)1×1图2-5f(3)递归调用流程变化示意图2.4递归算法分析2.4.1替换法2.4.2递归树法2.4.3主方法Chapter22.4递归算法分析Chapter2递归方程的求解一般可采用如下三种方法:

(1)替换法(SubstitutionMethod)(2)递归树法(RecursionMethod)(3)主方法(MasterMethod).当一个算法包含对自身的递归调用过程时,该算法的运行时间复杂度可用递归方程进行描述,求解该递归方程,可得到对该算法时间复杂度的函数度量。2.4.1替换方法Chapter2(1)替换方法替换方法的最简单方式为:根据递归规律,将递归公式通过方程展开、反复代换子问题的规模变量,通过多项式整理,如此类推,从而得到递归方程的解。2.4.1替换方法Chapter2例2.6汉诺塔算法(见例2.5)的时间复杂度分析。假设汉诺塔算法的时间复杂度为T(n),例2.5的算法递归方程为:2.4.1替换方法Chapter2利用替换法求解该方程:得到该算法的时间复杂度2.4.1替换方法Chapter2

例2.72-路归并排序的递归算法分析。假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到个长度为2(n为奇数时,最后一个序列的长度为1)的有序子序列;在此基础上,再对长度为2的有序子序列进行两两归并,得到若干个长度为4的有序子序列;如此重复,直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。2.4.1替换方法Chapter2两有序子序列合并为一个有序序列2-路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列,算法如下:voidMerge(RecordTyper1[],intlow,intmid,inthigh,RecordTyper2[]) /*已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列,将它们合并成一个有序序列,存放在r2[low..high]*/ {i=low;j=mid+1;k=low;while((i<=mid)&&(j<=high)) { if(r1[i].key<=r1[j].key) { r2[k]=r1[i];++i;} else { r2[k]=r1[j];++j;} ++k; } while(i<=mid) {r2[k]=r1[i];k++,i++;} while(j<=high); {r2[k]=r1[j];k++;j++;}}/*Merge*/2.4.1替换方法Chapter2在合并过程中,两个有序的子表被遍历了一遍,表中的每一项均被复制了一次。因此,合并的代价与两个有序子表的长度之和成正比,该算法的时间复杂度为O(n)。2-路归并排序的递归方法实现算法思想:将r1[]中的记录用归并法排序后放到r3[]中,可以分为下面三个步骤:①将r1[]前半段的记录用归并法排序后放到r2[]的前半段中;②将r1[]后半段的记录用归并法排序后放到r2[]的后半段中;③将r2[]的前半段和后半段合并到r3[]中。2.4.1替换方法Chapter22-路归并排序的完整算法如下:voidMSort(RecordTyper1[],intlow,inthigh,RecordTyper3[])/*r1[low….high]排序后放在r3[low….high]中,r2[low….high]为辅助空间*/{RecordType*r2; r2=(RecordType*)malloc(sizeof(RecordType)*(hight–low+1)); if(low==high)r3[low]=r1[low]; else{ mid=(low+high)/2;MSort(r1,low,mid,r2);MSort(r1,mid+1,high,r2);Merge(r2,low,mid,high,r3); } free(r2);}/*MSort*/2.4.1替换方法Chapter2二路归并排序算法的递归方程为:当n>1时,利用替换法,可得:2.4.1替换方法Chapter2取则(当n为奇数时,即可用替代)从而,即二次归并排序的算法时间复杂度为可将上述递归方程推广至一般形式,可记为:2.4.1替换方法Chapter2对该方程通过替换法求解:由可得到解一般形式为:2.4.1替换方法Chapter2若那么存在整数k,使有从而,当d(n)为常数时,有:当,c为常数时,有:即该递归方程的解为:其中2.4.1替换方法Chapter2推论:证明:①当时,,收敛,②当时,有所以③当时,则2.4.1替换方法Chapter2所以,

在上述二路归并算法的递归方程中,有利用推论公式②可直接得到算法的时间复杂度为。

替换方法求解递归方程还可以通过如下步骤进行:(1)猜测界限函数(2)对猜测进行证明,并寻找到猜测中常量C的范围。2.4.1替换方法Chapter2例2.8

利用替换方法解递归方程假设上界函数为O(nlog2n),假设该上界函数对于[n/2]是成立的,也就是说存在常数c,有T(n/2)≤c(n/2)log2(n/2)成立。现在需要证明T(n)≤cnlog2n。根据猜测,有:当c≥1时,上述结果成立下面证明猜测对于边界条件成立,即证明对于选择的常数c,对于边界条件成立。2.4.1替换方法Chapter2

假设T(1)=1是递归方程的惟一边界条件,那么对于 与发生矛盾。因此,归纳法中的归纳基础不成立。所以T(1)=1不能作为边界条件。由递归方程T(2)=2T(1)+2;T(3)=2T(1)+3;得T(2)和T(3)均依赖T(1),选择T(2)和T(3)作为归纳证明中的边界条件。由递归方程可得T(2)=4和T(3)=5算法复杂度的渐近表示法只要求对n≥n0,成立,因此可设n0=2,当n≥2时,成立。再选择c≥2,就会使得 和成立。以下对此进行证明:2.4.1替换方法Chapter2

当n=2k时,上式可写为T(n)=nT(1)+nlog2n,若n=2k-1,则上式展开时用T((n+1)/2)+T((n-1)/2)替代2T(n/2),用(n+1)/2+(n-1)/2代替n,同样可得到T(n)=nT(1)+nlog2n。由递归公式,T(1)=1,则 T(n)=n+nlog2n=nlog22+nlog2n=nlog2(2n)当n>=2时,要使得T(n)=nlog2(2n)<=cnlog2n则需 c>=log2(2n)/log2(n)当n=2时,由上式c>=2即可当n=3时,因log2(2n)/log2(n)=log2(6)/log2(3)<2,此时取c>=2满足条件。2.4.1替换方法Chapter2

当n>3时,此时取c>=2满足条件。由以上证明,当n>=2,c>=2时,成立。2.4.2递归树方法Chapter2

递归树的方法可以更好地猜测一个问题的解,并用替换方法证明这个猜测。图2-4表明了如何求解方程时构造递归树的方法,其中n假设假设为4的幂。图2-4递归树的构造过程(2)递归树方法2.4.2递归树方法Chapter2

深度为i的结点,其子问题的规模为n/4i,当n/4i=1时,子问题规模为1,这时位于树的最后一层(即i=log4n).在图2-4的递归树中,层数是从0开始算起的,第一层层数为0,最后一层的层数为log4n,共有log4n+1层。深度是从0开始算起的,第一层深度为0,最后一层深度为log4n,深度共为log4n+1。高度则是深度减1,为log4n。第i层的结点数为3i。(每一层的结点数是上一层结点数的三倍)层数为的每个结点的开销为(每一层子问题规模为上一层的1/4)2.4.2递归树方法Chapter2第i层上结点的总开销为层数为log4n的最后一层有个结点,每个结点的开销为T(1),该层总开销即将所有层的开销相加得到整棵树的开销:

2.4.2递归树方法Chapter2现在利用替换方法证明我们的猜测是正确的。假设这个界限对于n/4成立,即存在某个常数d,代入递归方程可得根据上面式子,当c≤(13/16)d时,有:2.4.3主方法Chapter2

主方法为我们提供了解如下形式递归方程的一般方法:其中a≥1,b>1为常数,f(n)是渐近正函数。算法将规模为n的问题划分成a个子问题,每个子问题的大小为n/b。求解这a个子问题,每个所需时间为T(n/b)。函数f(n)表示划分子问题与组合子问题解的开销。(3)主方法2.4.3主方法Chapter2例2.9,对于递归方程虽然划分后的子问题(n/b)并不一定为整数,但用T(n/b)取代或对递归方程的渐近行为无影响,所以在表示这种递归函数时略去了向上取整和向下取整函数。2.4.3主方法Chapter2定理2.1设a≥1,b>1为常数,f(n)为一函数。T(n)由以下递归方程定义:其中n为非负整数,则T(n)有如下的渐近界限:

(1)若对某些常数ε>0,有那么(2)若那么(3)若对某些常数ε>0有且对常数c<1与所有足够大的n,有那么2.4.3主方法Chapter2先来分析它的含义。在上述的每一种情况下,我们都把函数f(n)与函数进行比较,递归方程的解由这两个函数中较大的一个决定。第一种情形中,函数比函数f(n)更大,则解为:第二种情形中,这两个函数一样大,则解为:第三种情形中,f(n)是较大的函数,则解为:2.4.3主方法Chapter2我们还可以用图2-5表示方程(2.1),从另一个角度解释主定理。图2-5主定理的图示2.4.3主方法Chapter2图2-5所示树中叶子结点数为:

对于第一种情形,从根到叶结点开销的权重呈几何级数增加。叶结点占有整个权重的恒定比例。

对于第二种情形,每一层的权重大致相同。对于第三种情形,从根到叶结点开销的权重呈几何级数减小2.4.3主方法Chapter2例2.10解递归方程解:由递归方程可得,a=4,b=2且f(n)=n。因此,选取,则

递归方程满足主定理的第一种情形,因此2.5分治法的基本思想Chapter2

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。当问题规模n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。2.5分治法的基本思想Chapter2

分治法的特点:(1)子问题相互独立且与原问题形式相同;(2)反复分治,使划分得到的小问题小到不可再分 时,直接对其求解。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。2.6分治法的适用条件Chapter2

分治法所能解决的问题一般具有以下几个特征:⑴该问题的规模缩小到一定的程度就可以容易地解决;⑵该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。⑶利用该问题分解出的子问题的解可以合并为该问题的解;⑷该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。2.7分治法的基本步骤Chapter2

分治思想设计算法时一般包含的步骤

第一步,分解(割)。将待解决的问题划分成足够小的问题,相互独立,与原问题形式相同的子问题;第二步,求解。若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题第三步,合并。自下而上,将子问题的解逐层合并,得到原问题的解。2.7分治法的基本步骤Chapter2

分治法的一般算法框架为:

divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk;//分解问题for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}2.7分治法的基本步骤Chapter2在对采用分法思想设计的算法进行分析时,可用如下递归方程描述算法的运行时间T(n)。在该递归方程中,如果问题的规模足够小(n≤c),可以直接求解,则如果问题规模n>c,还需被分解为k个规模大小为n/m的子问题,且分析问题与合并问题解的时间分别为D(n)和C(n),则对于该方程,设n为m的幂,记D(n)=C1(n)+C2(n)则该递归方程的解为:2.8分治法典型示例2.8.1n个数中求出最大/最小值2.8.2快速排序2.8.3大整数乘法2.8.4折半查找2.8.5矩阵乘法Chapter22.8.1分治举例——n个数中求出最大最小值Chapter2问题描述:从给定的n个数中,设计算法在最坏情况下最多进行用次比较,可找出给定n个数的最大和最小值。问题分析:方法一:从n个数中找最大最小数可以通过如下过程进行:第一步,通过n-1次比较找出最大值;第二步,从其余的n-1个数中通过n-2次比较找出最小值。这种常规的方法一共要进行2n-3次比较((n-1)+(n-2))。要完成

2.8.1分治举例——n个数中求出最大最小值Chapter2

方法二:题目设计要求,可通过分治思想进行算法设计。记n个数的集合为S,将其平分为元素个数为n/2的两个集合S1,S2,。首先,分别在S1、S2中找出最大、最小值,分别记作MaxS1,MinS1,MaxS2,MaxS1;之后,通过2次比较,从所找到的该四个数中找出S中的最大、最小值,。从S1,S2中分别找出最大、最小值的方法可以按以上思想递归进行。 2.8.1分治举例——n个数中求出最大最小值Chapter2根据上述分析,采用分治递归思想设计的算法如下:VoidSearchMaxMin(S){if(|S|==2)return(max(a,b),min(a,b)) else{S分成S1,S2 (max1,min1)=SearchMaxMin(S1)//找出S1中最大、最小值

(max2,min2)=SearchMaxMin(s2)//找出S2中最大、最小值

return(max(max1,max2),min(min1,min2))//找出S中最大、最小值

} } 2.8.1分治举例——n个数中求出最大最小值Chapter2以下对该递归算法进行分析:(1).列出算法的递归方程。大小为n/2的2个集合分别递归比较(即2T(n/2)),所得分属2个集合的最大和最小值之间需再进行1次比较(即2次)。2.8.1分治举例——n个数中求出最大最小值Chapter2(2).求解递归方程。当n>2时令n=2k,则因为所以,从而2.8.1分治举例——n个数中求出最大最小值Chapter2(3).用数学归纳法证明是递归方程的解。当n=2时,T(2)=1=当n=2k时,若T(n)满足

当n=2k+1,时命题得证。由上例总结递归算法分析的三个步骤如下:首先,根据给出的递归算法列出递归方程;其次,推导求解递归方程;最后,证明所得到的解就是该递归方程的解。2.8.2分治举例——快速排序Chapter2问题描述:对给定的n个记录A[p..r]进行排序。问题分析:基于分治设计的思想,从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴,其关键字设为K1,然后将其余关键字小于K1的记录移到前面,而将关键字大于K1的记录移到后面,结果将待排序记录序列分成两个子表,最后将关键字为K1的记录插到其分界线的位置处。我们将这个过程称作一趟快速排序。2.8.2分治举例——快速排序Chapter2通过一次划分后,就以关键字为K1的记录为界,将待排序序列分成了两个子表,且前面子表中所有记录的关键字均不大于K1,而后面子表中的所有记录的关键字均不小于K1。对分割后的子表继续按上述原则进行分割,直到所有子表的表长不超过1为止,此时待排序记录序列就变成了一个有序表。具体的排序过程由以下三步组成:2.8.2分治举例——快速排序Chapter2

(1)划分:将数组A[p..r]划分成两个子数组A[p..q-1]和A[q+1..r](其中之一可能为空),满足数组A[p..q-1]中的每个元素值不超过数组A[q+1..r]中的每个元素。计算下标q作为划分过程的一部分。

(2)解决:递归调用快速排序算法,对两个子数组A[p..q-1]和A[q+1..r]进行排序。

(3)合并:由于子数组中元素已被排序,无需合并操作,整个数组A[p..r]有序。

2.8.2分治举例——快速排序Chapter2在该排序过程中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。2.8.2分治举例——快速排序Chapter2根据上述思想设计的算法:template<classType>voidQuickSort(TypeA[],intp,intr){ifp<rthenq←PARTITION(A,p,r);QuickSort(A,p,q-1);//对左半段排序

QuickSort(A,q+1,r);//对右半段排序

endif}2.8.2分治举例——快速排序Chapter2PARTITION(A,p,r)1x←A[p]//最最端元素作为枢轴元素2i←p-13forj←ptor-14doifA[j]≤x5theni←i+16exchangeA[i]A[j]7exchangeA[i+1]A[r]8returni+12.8.2分治举例——快速排序Chapter2假设待划分序列为A[left],A[left+1],…,A[right],具体实现上述划分过程时,可以设两个指针i和j,它们的初值分别为left和right。首先将基准记录A[left]移至变量x中,使A[left],即A[i]相当于空单元,然后反复进行如下两个扫描过程,直到i和j相遇:j从右向左扫描,直到A[j].key<x.key时,将A[j]移至空单元A[i],此时A[j]相当于空单元。i从左向右扫描,直到A[i].key>x.key时,将A[i]移至空单元A[j],此时A[i]相当于空单元。2.8.2分治举例——快速排序Chapter2

当i和j相遇时,A[i](或A[j])相当于空单元,且A[i]左边所有记录的关键字均不大于基准记录的关键字,而A[i]右边所有记录的关键字均不小于基准记录的关键字。最后将基准记录移至A[i]中,就完成了一次划分过程。对于A[i]左边的子表和A[i]右边的子表可采用同样的方法进行进一步划分。图2-6给出了一个表示第一次划分过程的实例。2.8.2分治举例——快速排序Chapter2

4862357755143598

x

4862357755143598low highlow62357755143598 highlow high35623577551498low high35623577551498low high35357755146298(a)一趟快速排序2.8.2分治举例——快速排序Chapter2lowhigh35357755146298lowhigh35143577556298lowhigh3514357755629835143555776298lowhigh35143555776298lowhigh 3514354855776298lowhigh(a)一趟快速排序2.8.2分治举例——快速排序Chapter2初始状态:4862357755143598一次划分后:{351435}48{55776298}分别进行快速排序:{14}35{35}结束结束55{776298} {62}77{98}

结束结束(b)快速排序全过程

图2-6快速排序过程示例2.8.2分治举例——快速排序Chapter2快速排序最坏情况分析当划分过程产生的两个子问题规模分别为n-1和1时,快速排序出现最坏的情况。划分的时间复杂度为O(n)。假设每次递归调用时产生这种不平衡的情况。间复杂度为Θ(n),因为对规模为0的数组的递归调用只会返回,(1)列出该算法最坏情况下的递归方程(2)求解递归方程当n>1时,2.8.2分治举例——快速排序Chapter2即,在最坏情况下,该算法的时间复杂度为O(n2)。(3)证明n2是递归方程的解当n=1时T(1)=1假设当n=k时,当n=k+1时,2.8.2分治举例——快速排序Chapter2

即(k+1)2是递归方程的解。所以,n2是递归方程的解。因此,快速排序最坏情况下的运行时间不比冒泡排序的运行时间好,而最坏情况是在输入已经完全有序(升序)时出现的。2.8.2分治举例——快速排序Chapter2快速排序最好情况分析在大多数均匀划分的情况下,PARTITION产生两个规模为n/2的子问题,以下对该情况下的算法进行分析。(1)列出递归方程(2)求解递归方程2.8.2分治举例——快速排序Chapter2设n=2k,则

T(n)=n+nlog2n=O(nlog2n)

直接利用2.4节中的推论,也可得到该递归方程的解为T(n)=O(nlog2n)。也可以通过2.4节中的主方法进行递归方程求解,递归方程符合主方法的第2种情形,可知该递归方程的解为T(n)=O(nlog2n)。2.8.2分治举例——快速排序Chapter2(3)证明nlog2n是递归方程的解当时假设时,成立则当n>m时,不妨有:2.8.2分治举例——快速排序Chapter2所以,nlog2n为递归方程的解。上述折半查找递归算法分析结果表明,如果划分在算法的每一层递归上产生两个相同规模的问题,则得是快速排序算法的最佳情况。2.8.3分治举例——大整数乘法Chapter2问题描述:设有两个n位二进制数x,y,现要计算他们的乘积xy;问题分析:两个n位二进制整数相乘,根据计算规则,两个数中每位数都需要对应做乘法运算,因此,按照一般方法计算这两个数乘法所需要的算法的复杂度是现采用分治思想进行处理降低算法:设有两个n位二进制数x,y均为位。

其做了四次位的乘法,3次超过位的整数加法,运算级别为2.8.3分治举例——大整数乘法Chapter2(1)列出上述过程的递归方程(2)求解递归方程:当n>1时,设n=2k,则k=log2n即,T(n)=O(n2)2.8.3分治举例——大整数乘法Chapter2(3)证明n2是该递归方程的解当时,假设时,成立则当n>m时,不妨,有:2.8.3分治举例——大整数乘法Chapter2从而,T(n)=O(n2)得证。在该算法中,通过分治法进行了4次位的乘法运算,但根据算法分析结果可知,并没有改进算法的性能,算法时间复杂度仍为O(n2)。该算法性能的提升,需要减少乘法算运次数,可以通过以下方式进行:先计算:,,则那么,在计算过程中,一共进行了3次位的乘法运算,6次加减法和2次移位。2.8.3分治举例——大整数乘法Chapter2按上述改进,得到大整数乘法的完整算法:longMULT(x,y,n){longs=SIGN(x)*SIGN(y);//计算结果符合

x=abs(x);y=abs(y);if(n==1){if(x==0||y==0)return0;elsereturns;}

2.8.3分治举例——大整数乘法Chapter2else{a=x的左边n/2位;

b=x的右边n/2位;

c=y的左边n/2位;

d=y的右边n/2位;

m1=MULT(a,c,n/2);m2=MULT(a-b,d-c,n/2);m3=MULT(b,d,n/2);s=s*(m1*2n+(m1+m2+m3)*2n/2+m3)returns;}}2.8.3分治举例——大整数乘法Chapter2(1)列出算法的递归方程:(2)求解递归方程当n>1时,设n=2k,则k=log2n2.8.3分治举例——大整数乘法Chapter2即也可以通过2.4节中的主方法求解该递归方程:根据定理1,该递归方程中a=3,b=2,T(n)=O(nlog23)2.8.3分治举例——大整数乘法Chapter2因为,满足主方法中的第(1)种情况,因此结果表明,我们通过降低计算过程中的乘法运算的次数,降低了该算法的复杂度,使其更优。(3)证明上述求解结果:当时,假设时,成立。则当n>m时,不妨,有:从而得证。2.8.3分治举例——大整数乘法Chapter2例2.13:分析:2.8.4分治举例——折半查找Chapter2问题描述:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。问题分析:采用分治的思想,充分利用元素之间的已存在的次序关系,将排好序的数组a[0:n-1]划分成两个个数相同的左、右两部份,取a[n/2]与x进行比较,如果x=a[n/2],则找到x,算法结束;如果x>a[n/2],则在数组a划分得到的右半部继续查找;如果x<a[n/2],则在数组a划分得到的左半部继续查找。在数组a左半部或右半部分继续查找x的过程采用同样的分治方法。2.8.4分治举例——折半查找Chapter2按照上述思想,二分搜索算法为:ITERATIVEBINARYSEARCH(A,v,low,high)1whilelow≤high2domid←(low+high)/23ifv=A[mid]4thenreturnmid5elseifv>A[mid]6thenlow←mid+17elsehigh←mid-18returnNIL2.8.4分治举例——折半查找Chapter2(1)列出该算法的递归方程:(2)利用替换法求解该递归方程:当n>1时2.8.4分治举例——折半查找Chapter2

设n=2k,即k=log2n得到该递归方程的解为T(n)=1+log2n=O(log2n),即该算法的时间复杂度为O(log2n)。对于该算法,我们也可以对语句执行频度进行分析。可看出,该算法中每执行一次while循环,待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(log2n)趟。循环体内运算需要O(1)时间,因此整个算法在最坏情况下的计算时间复杂度为O(log2n)。2.8.4分治举例——折半查找Chapter2(3)证明log2n是递归方程的解当n=1时T(n)=1假设当n=m时,T(m)=1+log2m=O(log2m)成立当n>m时,不妨n=2m从而证明了log2n是该递归方程的解。2.8.5分治举例——矩阵乘法Chapter2

问题描述:设计算法,完成矩阵运算C=A×B,其中A、B为n×n矩阵。矩阵乘法是线性代数中最基本的运算之一,它在数值计算中有广泛的应用。若A和B是2个n×n矩阵。A和B的乘积矩阵C中的元素为:问题分析:根据该规则,两个n阶矩阵相乘时,算法需要完成3重次数为n的循环,算法的时间复杂度为,可以利用分治法对算法进行改进:2.8.5分治举例——矩阵乘法Chapter2

设即:

C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22则C=A×B可划分为如下形式2.8.5分治举例——矩阵乘法Chapter2

n=2时,直接求时,求子阵乘积,要做8个n/2子阵相乘,4个n/2子阵相加,后者的时间复杂度为O(n2)。(1)列出以上分治方法的递归方程2.8.5分治举例——矩阵乘法Chapter2

(2)求解决递

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论