算法设计与分析课件.ppt
《算法设计与分析课件.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析课件.ppt(71页珍藏版)》请在三一办公上搜索。
1、,第一章 算法概述,第二章 递归与分治策略,第三章 动态规划,第四章 贪心算法,第五章 回朔法,第六章 分支限界法,第七章 概率算法,算法设计与分析 目录,1,第一章 算法概述第二章 递归与分治策略第三章 动态规划,算法设计与分析 递归与分治,2.1 递归的概念,直接或间接地调用自身的算法称为递归算法。由分治法产生的子问题往往是原问题的较小模式,为使用递归技术提供了方便。反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解,自然导致递归过程的产生。,2,算法设计与分析 递归与分治2.1 递归的概念直接或间接地,算法设计与分析 递归与分治,相关概
2、念当子问题足够大,需要递归求解时,称为递归情况;当子问题足够小时,不再需要递归时,递归进入“触底”,进入基本情况;用函数自身给出定义的函数称为递归函数;递归式是一个等式或不等式,它通过更小的输入上的函数值来描述一个函数.,3,算法设计与分析 递归与分治相关概念3,递归函数的内部执行过程,(1)运行开始时,为递归调用建立一个工作栈,其结构包括实参、局部变量和返回地址;(2)每次执行递归调用之前,把递归函数的实参和局部变量的当前值以及调用后的返回地址压栈;(3)每次递归调用结束后,将栈顶元素出栈,使相应的实参和局部变量恢复为调用前的值,然后转向返回地址指定的位置继续执行,算法设计与分析 递归与分治
3、,4,递归函数的内部执行过程(1)运行开始时,为递归调用建立一个,算法设计与分析 递归与分治,例2-3 Ackerman函数当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数。Ackerman函数A(n,m)定义如下:,该变量是由函数自身定义,5,算法设计与分析 递归与分治例2-3 Ackerman函数,分析:A(n,m)的自变量m的每一个值都定义了一个单变量函数:M=0时,A(n,0)=n+2M=1时 A(1,1)=2 和 A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,故A(n,1)=2*n(上式是一个递推公式,每当n-1便加2)M=2时,A(1,2)=A(
4、A(0,2),1)=A(1,1)=2 A(n,2)=A(A(n-1,2),1)=2A(n-1,2),故A(n,2)=2n。M=3时,类似的可以推出M=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。,算法设计与分析 递归与分治,6,分析:算法设计与分析 递归与分治6,算法设计与分析 递归与分治,1、证明 A(1,1)=2因为n,m=1使用递推式(4)得 A(1,1)=A(A(0,1),0)由A(0,m)=1,故 A(1,1)=A(1,0)由(1)式 A(1,0)=2 所以A(1,1)=2,2、证明A(n,1)=2n(n=1)因为n,m=1 使用递归式(4)得A(n,
5、1)=A(A(n-1,1),0)由公式(3)A(n,1)=A(n-1,1)+2由此式看出m=1 时,n每降一阶就增加2,一直降到n=1 即A(1,1)共增加n个2,n 个2相加和为2n所以A(n,1)=2n,7,算法设计与分析 递归与分治1、证明 A(1,1)=22、证,算法设计与分析 递归与分治,3、证明当m=2时 A(n,2)=2n由递推式(4)A(n,2)=A(A(n-1,2),1),此时已经演变为m=1的情况,式中A(n-1,2)相当于2节中的n的位置,因此利用2节的结论有 A(n,2)=2A(n-1,2)可以看出随着n的降阶会增长2的倍数,那么当n降为1时即A(1,2)的情况如何呢?
6、根据递推式(4)有A(1,2)=A(A(0,2),1),再由公式(2)A(0,m)=1故A(1,2)=A(1,1)=2所以A(n,2)随着n的降阶每次乘2,共乘n次得A(n,2)=2n公式得证,8,算法设计与分析 递归与分治3、证明当m=2时 A(n,2),定义单变量的Ackerman函数A(n)为:A(n)=A(n,n)。定义其拟逆函数(n)为:(n)=minkA(k)n。即(n)是使nA(k)成立的最小的k值。(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有(n)4。但在理论上(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。,算法设计与分析 递归与分治,9,定义单变
7、量的Ackerman函数A(n)为:算法设计与分析,递归树,T(n)=3T(n/4)+O(n 2),算法设计与分析 递归与分治,10,递归树T(n)=3T(n/4)+O(n 2)算法设,算法设计与分析 递归与分治,11,算法设计与分析 递归与分治11,补充:主方法(定理),求解这类递推式的方法是主方法,主方法依赖于下面的主定理,使用主定理可直接得到递推式的解。定理(主定理):a1且b1是常数,f(n)是一个函数,T(n)由如下的递推式定义:T(n)=aT(n/b)+f(n),式中,n/b指n/b或n/b,则T(n)有如下的渐近界:(1)若对于某常数0,有f(n)=O(nlogba-),则T(n
8、)=(nlogba);(2)若f(n)=(nlogba),则T(n)=(nlogbalogn);(3)若对于某常数0,有f(n)=(nlogba+),且对于某个常数c1和所有足够大的n,有af(n/b)cf(n),则T(n)=(f(n)。,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,12,补充:主方法(定理)求解这类递推式的方法是主方法,主方法依赖,定理(主定理):a1且b1是常数,f(n)是一个函数,T(n)由如下的递推式定义:T(n)=aT(n/b)+f(n),式中,n/b指n/b或n/b,则T(n)有如下的渐近界:(1)若对于某常数0,有f(n)=O(nlogba-)
9、,则T(n)=(nlogba);,举例:,T(n)=16T(n/4)+n,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,13,定理(主定理):a1且b1是常数,f(n)是一个函数,定理(主定理):a1且b1是常数,f(n)是一个函数,T(n)由如下的递推式定义:T(n)=aT(n/b)+f(n),式中,n/b指n/b或n/b,则T(n)有如下的渐近界:(2)若f(n)=(nlogba),则T(n)=(nlogbalogn);,举例:,T(n)=T(3n/7)+1,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,14,定理(主定理):a1且b1是常数,f(n)是
10、一个函数,定理(主定理):a1且b1是常数,f(n)是一个函数,T(n)由如下的递推式定义:T(n)=aT(n/b)+f(n),式中,n/b指n/b或n/b,则T(n)有如下的渐近界:(3)若对于某常数0,有f(n)=(nlogba+),且对于某个常数c1和所有足够大的n,有af(n/b)cf(n),则T(n)=(f(n)。,举例:,T(n)=3T(n/4)+nlogn,T(n)=aT(n/b)+f(n),算法设计与分析 递归与分治,15,定理(主定理):a1且b1是常数,f(n)是一个函数,递归小结,优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序
11、带来很大方便。,缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,算法设计与分析 递归与分治,16,递归小结优点:结构清晰,可读性强,而且容易用数学归纳法来证明,解决方法:在递归算法中消除递归调用,使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归,只不过人工做了本来由编译器做的事情,优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为尾递归,从而迭代求出结果。后两种方法在时空复杂度上均有较大改善,但其适用范围有限。,算法设计与分析 递归与分治,17,解决方法:在递归算法中消除递
12、归调用,使其转化为非递归算法。算,尾递归是在递归调用时“积累”之前调用的结果,并将其传入下一次递归调用中,将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中.,算法设计与分析 递归与分治,尾递归只会占用恒量的内存,形式上只要最后一个return语句是单纯函数就可以,18,尾递归是在递归调用时“积累”之前调用的结果,并将其传入下一次,2.2分治法的基本思想,算法设计与分析 递归与分治,将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易
13、求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。,19,2.2分治法的基本思想算法设计与分析 递归与分治将一个规模,算法设计与分析 递归与分治,20,子问题1 子问题1的解 子问题2的解 子问题2,算法设计与分析 递归与分治,问题(N个输入),相同类型,合并解,分治法要求分解成同类子问题,并允许不断分解,使问题规模逐步减小,最终可用已知的方法求解足够小的问题。,21,算法设计与分析 递归与分治问题(N个输入)子问题1子问题2,算法设计与分析 递归与分治,举例:二路归并排序,分解过程:对任意长度为n的序列排序,首先将问题不断分解,直至问题可直接求
14、解。长度为n的序列分解为2个n/2的子序列,依次循环,直至分解为n个长度为1的序列,显然长度为1的序列是有序表。合并过程:将已排序的的子序列不断合并,形成长度为n的排序序列。然后反复进行两两归并为n/2个有序表;再对n/2个有序表两两归并,循环直到得到长度为n的有序线性表。,22,算法设计与分析 递归与分治举例:二路归并排序分解过程:对任,算法设计与分析 递归与分治,template void MergeSort(Type a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 MergeSort(a,left,
15、i);/对前半部分排序 MergeSort(a,i+1,right);/对后半部分排序 Merge(a,b,left,i,right);/合并到数组b Copy(a,b,left,right);/复制回数组a,合并步,将有序表aleft,i和ai+1,right合并到bleft,right,问题分解:规模为原来的一半;问题性质不变。,23,算法设计与分析 递归与分治template class,template void MergeSort(Type a,int left,int right)if(leftright)int i=(left+right)/2;MergeSort(a,left,
16、i);MergeSort(a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);,分析:二路归并排序的时空复杂性,算法设计与分析 递归与分治,时间复杂度T(n)cT(n/2)T(n/2)O(n)O(n),void Merge(Type c,Type d,int i,int m,int r)int la,lb,lc;la=i;lb=m+1;lc=i;while(la=m,24,template 分析:二路归并,二路归并排序算法存在以下递推式:,解此递归方程,二路归并排序的时间复杂度是O(nlogn)。二路归并排序其空间复杂性为O(n)
17、。,算法设计与分析 递归与分治,25,二路归并排序算法存在以下递推式:解此递归方程,二路归并排序的,算法设计与分析 递归与分治,总结:分治法的适用条件,分治法所能解决的问题一般具有以下特征:该问题规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同子问题,即该问题具有最优子结构性质;利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。,应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用。,关键特征,能否利用分治法完全取决于问题是否具有第四条特征,如果具备了第一条和第二条特征,而不具
18、备第四条特征,则可以考虑贪心法或动态规划法。,26,算法设计与分析 递归与分治总结:分治法的适用条件分治法所能,算法设计与分析 递归与分治,分治法的基本步骤:,划分:把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题,有时也可用循环来实现。合并:把各个子问题的解合并起来。,27,算法设计与分析 递归与分治分治法的基本步骤:划分:把规模为,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller
19、subinstances P1,P2,.,Pk;/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解,分治法的基本步骤,算法设计与分析 递归与分治,在用分治法设计算法时,最好使子问题的规模大致相同,即,将一个问题分成大小相等的k个子问题(许多问题取k=2)。使子问题规模大致相等的做法是出自一种平衡子问题的思想,这通常比子问题规模不等的做法要好。,|P|问题P的规模n0为阀值adhoc(P)基本子算法,28,divide-and-conquer(P)分治法的基
20、本步骤算,分治法的复杂性分析,从一般设计模式看,用分治法设计的程序通常是一个递归算法。分治法将规模为n的问题分成k个规模为n/m的子问题:设n0=1,且adhoc解问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。,用T(n)(递归方程)表示该分治法求解规模为|P|=n的问题所需的计算时间:,算法设计与分析 递归与分治,29,分治法的复杂性分析从一般设计模式看,用分治法设计的程序通常是,通过迭代法求得方程解:,基本子问题花费时间,合并步花费时间,算法设计与分析 递归与分治,30,通过迭代法求得方程解:基本子问题花费时间合并
21、步花费时间 算法,2.3 二分搜索技术,算法设计与分析 递归与分治,问题描述:已知一个按非降次序排列的元素表a1,a2,an,判定某个给定元素x是否在该表中出现,若是,则找出该元素在表中的位置,并置于j,否则,置j为0。一般解决方法:从头到尾查找一遍。,x,成功与不成功的最坏情况下需O(n)次比较,31,2.3 二分搜索技术算法设计与分析 递归与分治问题描述:已,分析:如果n=1即只有一个元素,则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析:比较x和a的中间元素amid,若x=amid,则x在L中的位置就是mid;如果xai,同理我们只要在amid的
22、后面查找x即可。无论是在前面还是后面查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析:很显然此问题分解出的子问题相互独立,即在ai的前面或后面查找x是独立的子问题,因此满足分治法的适用条件。,分析:,该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解;分解出的各个子问题是相互独立的。,算法设计与分析 递归与分治,32,分析:如果n=1即只有一个元素,则只要比较这个元素和x就可以,二分搜索算法:template int BinarySearch(Ty
23、pe a,const Type,算法复杂度分析:每执行一次算法的while循环,待搜索数组的大小减少一半。在最坏情况下,while循环被执行O(logn)次,循环体内运算需要O(1)时间。算法在最坏情况下的计算时间复杂性为O(logn)。,算法设计与分析 递归与分治,33,二分搜索算法:算法复杂度分析:算法设计与分析 递归与分治3,2.8 快速排序,算法思路 对Ap:r,按以下步骤进行排序:(1)分解:取A中一元素为支点,将Ap:r分成3段:Ap:q-1,Aq,A q+1:r,其中A p:q-1中元素Aq,Aq+1:r中元素 Aq;(2)求解:通过递归调用分别对Ap:q-1和Aq+1:r 排序
24、。(3)合并:合并A p:q-1,Aq,A q+1:r 为Ap:r。,算法设计与分析 递归与分治 快速排序,34,2.8 快速排序算法思路 对Ap:r,按以下步骤进行,得:Tmax(n)=O(n2),快速排序算法,template void QuickSoft(T a,int p,int r)if(pr)int q=Partition(a,p,r)QuickSort(a,p,q-1);/对左半段排序 QuickSoft(a,q+1,r);/对右半段排序,template int Partion(T a,int p,int r)int i=p;j=r+1;t x=ap;/取支点/将x的元素交换到
25、左边/将x的元素交换到右边 while(true)while(a+i x);if(i=j)break;swap(ai,aj);ap=aj;aj=x;return j,Tmin(n)=,O(1)n1,得:Tmin(n)=O(nlogn),复杂性分析,Tmax(n)=,O(1)n1,35,得:Tmax(n)=O(n2)快速排序算法,随机选择支点的快速排序,template void randomizedQuickSoft(T a,int p,int r)if(pr)int q=randomizedPartition(a,p,r)randomizedQuickSort(a,p,q-1);/对左半段排
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 课件

链接地址:https://www.31ppt.com/p-2073784.html