算法设计与分析PPT课件.ppt
- 文档编号:9986261
- 上传时间:2023-05-22
- 格式:PPT
- 页数:390
- 大小:4.10MB
算法设计与分析PPT课件.ppt
《算法设计与分析PPT课件.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析PPT课件.ppt(390页珍藏版)》请在冰点文库上搜索。
算法设计与分析,2,课程目的,对算法设计与分析进行一个较为全面的介绍,使大家具有进行简单的算法设计与分析的基本能力,先修课程,程序设计语言数据结构高等数学,离散数学概率论,3,主要内容介绍,第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理论,4,教学用书,王晓东算法设计与分析清华大学出版社,5,T.Cormen,C.Leiserson,R.Rivest,andC.SteinIntroductiontoAlgorithms,2ndEd.MITPressandMcGraw-HillBookCompany,2001,教学参考书,6,D.E.KnuthTheArtofComputerProgramming,Vol.1and3,ThirdEdition,AddisonWesley,1997.,7,第1章算法引论,程序=算法+数据结构,1.1算法与程序,一.算法在计算机科学中的重要地位,8,二.算法的基本概念,一个有穷规则的有序集合称为一个算法。
1.定义.,2.算法的特征.,输入:
有零个或多个外部量作为算法的输入。
输出:
算法产生至少一个量作为输出。
确定性:
组成算法的每条指令清晰、无歧义。
有限性:
算法中每条指令的执行次数有限。
可行性:
执行每条指令的时间也有限。
9,例.,求正整数m、n的最大公因数。
解一.,
(1)求余数:
用m除以n,得余数r(0rn)。
(2)判断余数:
若余数r=0,输出n,结束。
否则,转(3)。
(3)更新被除数和除数:
mn,nr,转
(1)。
10,解二.,输入m、n,r=m%n,mn,nr,输出n,是,否,11,解三.,Euclid(intm,intn)intr;while(n!
=0)r=m%n;m=n;n=r;printf(“%d”,m),12,3.算法的描述方法.,
(1)自然语言,
(2)流程图,(3)程序设计语言,13,三.算法设计与分析的步骤,1.问题的描述.,2.模型的选择.,3.算法设计和正确性证明.,4.算法的分析.,5.算法的实现.,14,1.2算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用n、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那么,应该有C=F(n,I,A)。
一般把时间复杂性和空间复杂性分开,并分别用T和S来表示,则有:
T=T(n,I)和S=S(n,I)。
(通常,让A隐含在复杂性函数名当中),15,最坏情况下的时间复杂度:
渐近时间复杂度:
平均情况下的时间复杂性:
设Dn是规模为n的合法输入的集合;I*是Dn中使T(n,I*)达到Tmax(n)的合法输入;而P(I)是在算法的应用中出现输入I的概率。
则:
n时,T(n)的主要部分,算法共有k种基本步骤,第i种步骤所需时间ti,出现次数ei.,用问题体积n表示的运行时间T(n)称为时间复杂度,16,算法复杂度的重要性,假设计算机每秒可作1000次基本运算,17,有效算法,最佳算法,计算问题的分类,1.无法写出算法的问题.,2.有多项式算法的问题.,3.介于上述两问题之间的问题.,18,例,解,用最直观的方法,用Horner算法,Horner(intan+1,realx)intp=an;for(i=1;i=n;i+)p=p*x+an-i;returnp;,19,表示算法渐近复杂度的数学符号:
渐近意义下的记号:
O、o设f(n)和g(n)是定义在正数集上的正函数。
O的定义:
如果存在正的常数C和自然数N0,使得当nN0时有f(n)Cg(n),则称函数f(n)当n充分大时上有界,且g(n)是它的一个上界,记为f(n)=O(g(n)。
即f(n)的阶不高于g(n)的阶。
根据O的定义,容易证明它有如下运算规则:
(1)O(f)+O(g)=O(max(f,g);
(2)O(f)+O(g)=O(f+g);(3)O(f)O(g)=O(fg);(4)如果g=O(f),则O(f)+O(g)=O(f);(5)O(Cf)=O(f),其中C是一个正的常数;(6)f=O(f)。
20,的定义:
如果存在正的常数C和自然数N0,使得当nN0时有f(n)Cg(n),则称函数f(n)当n充分大时下有界,且g(n)是它的一个下界,记为f(n)=(g(n)。
即f(n)的阶不低于g(n)的阶。
的定义:
定义f(n)=(g(n)当且仅当f(n)=O(g(n)且f(n)=(g(n)。
此时称f(n)与g(n)同阶。
o的定义:
对于任意给定的0,都存在正整数N0,使得当nN0时有f(n)/g(n),则称函数f(n)当n充分大时的阶比g(n)低,记为f(n)=o(g(n)。
例如,4nlogn+7=o(3n2+4nlogn+7)。
21,第2章递归与分治策略,凡治众如治寡,分数是也。
-孙子兵法,22,2.1递归的概念,直接或间接地调用自身的较小模式的算法称为递归算法。
用函数自身的较小模式给出其定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式,子问题的复杂度也原问题复杂度的较小模式,这就为使用递归技术进行算法分析提供了方便。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
23,例1阶乘函数阶乘函数可递归地定义为:
边界条件,递归方程,边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。
下面来看几个实例:
factorial(intn)if(n=0)return1;elsereturnfactorial(n-1);,24,阶乘函数可以找到相应的非递归方式定义:
factorial(intn)inti,p=1;for(i=1;i=n;i+)p=p*i;returnp;,25,例2Fibonacci数列,26,Fibonacci数列的前10项为1,1,2,3,5,8,13,21,34,55,它可以递归地定义为:
边界条件,递归方程,第n个Fibonacci数可递归地计算如下:
fibonacci(intn)if(n=1)return1;elsereturnfibonacci(n-1)+fibonacci(n-2);,27,生成函数法!
Fibonacci函数也可以找到相应的非递归方式定义:
28,例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数。
Ackerman函数A(n,m)定义如下:
Ackerman函数无法找到非递归的定义。
29,Ackerman函数A(n,m)的自变量m的每一个值都定义了一个单变量函数:
m=0时,A(n,0)=n+2m=1时,由A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n1),和A(1,1)=2,得A(n,1)=2*nm=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)=。
m=3时,类似的可以推出m=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。
30,定义单变量的Ackerman函数A(n)为,A(n)=A(n,n)。
定义其拟逆函数(n)为:
(n)=minkA(k)n。
即(n)是使nA(k)成立的最小的k值。
(n)在复杂度分析中常遇到。
对于通常所见到的正整数n,有(n)4。
但在理论上(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。
31,例4排列的生成问题设计一个递归算法生成n个元素r1,r2,rn的全排列。
设R=r1,r2,rn是要进行排列的n个元素,Ri=Rri。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。
R的全排列可归纳定义如下:
当n=1时,perm(R)=(r),其中r是集合R中唯一的元素;当n1时,perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)构成。
32,perm(list,intk,intm)/产生前缀是list0:
k-1,后缀是listk:
m的所有排列/perm(list,0,n-1)产生list0:
n-1的去全排列if(k=m)/单元素排列for(inti=0;i=m;i+)coutlisti;coutendl;else/多元素序列,递归产生排列for(inti=k;i=m;i+)swap(listk,listi);perm(list,k+1,m);swap(listk,listi);,33,例.产生123的所有排列,34,35,例5整数划分问题将正整数n表示成一系列正整数之和:
n=n1+n2+nk,其中n1n2nk1,k1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分:
6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。
36,设q(n,m)为n的最大加数n1不大于m的划分个数。
则:
(1)q(n,1)=1,n1;,
(2)q(n,m)=q(n,n),nm;,(4)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。
(5)q(n,m)=q(n-m,m)+q(n,m-1),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1的划分组成。
(3)q(1,m)=1,m1;,37,显然,正整数n的划分数p(n)=q(n,n)。
q(intn,intm)if(m=1|n=1)return1;elseif(nm)returnq(n,n);elseif(n=m)return1+q(n,n-1);elsereturnq(n,m-1)+q(n-m,m);,38,例6Hanoi塔问题设a,b,c是3个塔座。
开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。
各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则:
规则1:
每次只能移动1个圆盘;规则2:
任何时刻都不允许将较大的圆盘压在较小的圆盘之上;规则3:
在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。
39,hanoi(intn,inta,intb,intc)/将塔座a上的盘子移到塔座b上,塔座c为辅助塔座if(n0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);,40,例.描述n=3时,hanoi(n,a,b,c)的运行过程。
41,42,43,递归小结,优点:
结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:
递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
44,递归小结,解决方法:
在递归算法中消除递归调用,使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。
该方法通用性强,但本质上还是递归,只不过人工做了本来由编译器做的事情,优化效果不明显。
2.用递推来实现递归函数。
3.通过Cooper变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善,但其适用范围有限。
45,将问题分为a个子问题,对这a个子问题分别求解。
如果子问题的规模仍然不够小,则每个子问题再划分为a个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。
2.2分治法的基本思想,46,将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
分治算法的程序具有递归的特点,47,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征:
该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
因为问题的计算复杂性一般是随着问题规模的增加而增加,因此大部分问题满足这个特征。
这条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征,如果具备了前两条特征,而不具备第三条特征,则可以考虑贪心算法或动态规划。
这条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然也可用分治法,但一般用动态规划较好。
48,分治法的基本步骤,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题dividePintosmallersubinstancesP1,P2,.,Pa;/分解问题for(i=1,i=a,i+)yi=divide-and-conquer(Pi);/递归的解各子问题returnmerge(y1,.,ya);/将各子问题的解合并为原问题的解人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。
即将一个问题分成大小相等的a个子问题的处理方法是行之有效的。
这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。
49,分治法的复杂性分析,一个分治法将规模为n的问题分成a个规模为n/b的子问题去解。
设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为a个规模为b的子问题以及用merge将这a个子问题的解合并为原问题的解需用f(n)个单位时间。
用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:
通过迭代法求得方程的解:
注意:
递归方程及其解只给出n等于b的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于b的方幂时T(n)的值可以估计T(n)的增长速度。
通常假定T(n)是单调上升的,从而当binbi+1时,T(bi)T(n)T(bi+1)。
50,51,ifT(n)=aT(n/b)+f(n)then,TheMasterTheorem,52,53,54,55,2.3二分搜索技术,分析:
如果n=1即只有一个元素,则只要比较这个元素和x就可以确定x是否在表中。
因此这个问题满足分治法的第一个适用条件,分析:
比较x和a的中间元素amid,若x=amid,则x在L中的位置就是mid;如果xai,同理我们只要在amid的后面查找x即可。
无论是在前面还是后面查找x,其方法都和在a中查找x一样,只不过是查找的规模缩小了。
这就说明了此问题满足分治法的第二个和第三个适用条件。
分析:
很显然此问题分解出的子问题相互独立,即在ai的前面或后面查找x是独立的子问题,因此满足分治法的第四个适用条件。
给定已按升序排好序的n个元素a0:
n-1,现要在这n个元素中找出一特定元素x。
分析:
该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解;分解出的各个子问题是相互独立的。
56,给定已按升序排好序的n个元素a0:
n-1,现要在这n个元素中找出一特定元素x。
据此容易设计出二分搜索算法:
BinarySearch(inta,intx,intn)/在a0amiddle)left=middle+1;elseright=middle-1;return-1;/未找到x,算法复杂度分析:
每执行一次算法的while循环,待搜索数组的大小减少一半。
因此,在最坏情况下,while循环被执行了O(log2n)次。
循环体内运算需要O
(1)时间,因此整个算法在最坏情况下的计算时间复杂性为O(log2n)。
57,2.4大整数的乘法,请设计一个有效的算法,可以进行两个n位大整数的乘法运算,小学的方法:
O(n2)效率太低分治法:
复杂度分析T(n)=O(n2)没有改进,58,由:
XY=ac2n+(ad+bc)2n/2+bd得:
XY=ac2n+(a-b)(d-c)+ac+bd)2n/2+bd或:
XY=ac2n+(a+b)(c+d)-ac-bd)2n/2+bd,复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进,细节问题:
两个XY的复杂度都是O(nlog3),但考虑到a+c,b+d可能得到m+1位的结果,使问题的规模变大,故不选择第2种方案。
为了降低时间复杂度,必须减少乘法的次数。
59,请设计一个有效的算法,可以进行两个n位大整数的乘法运算,小学的方法:
O(n2)效率太低分治法:
O(n1.59)较大的改进更快的方法?
如果将大整数分成更多段,用更复杂的方式把它们组合起来,将有可能得到更优的算法。
最终的,这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。
该方法也可以看作是一个复杂的分治算法,对于大整数乘法,它能在O(nlogn)时间内解决。
是否能找到线性时间的算法?
目前为止还没有结果。
60,2.5Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:
若依此定义来计算A和B的乘积矩阵C,则每计算C的一个元素Cij,需要做n次乘法和n-1次加法。
因此,算出矩阵C的个元素所需的计算时间为O(n3),传统方法,61,使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。
由此可将方程C=AB重写为:
分治法,由此可得:
复杂度分析T(n)=O(n3)没有改进,62,为了降低时间复杂度,必须减少乘法的次数。
复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进,63,传统方法:
O(n3)分治法:
O(n2.81)更快的方法?
Hopcroft和Kerr已经证明(1971),计算2个矩阵的乘积,7次乘法是必要的。
因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算22矩阵的7次乘法这样的方法了。
或许应当研究或矩阵的更好算法。
在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。
目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法?
目前为止还没有结果。
64,2.6棋盘覆盖,在一个2k2k个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
65,算法,当k0时,将2k2k棋盘分割为4个2k-12k-1子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。
为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如(b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。
递归地使用这种分割,直至棋盘大小为11。
66,程序代码,ChessBoard(inttr,inttc,intdr,intdc,intsize)/tr、tc:
棋盘左上角方格的行号、列号/dr、dc:
特殊方格的行号、列号if(size=1)return;intt=tile+;/L型骨牌号,tile初值为1ints=size/2;/分割棋盘/用L型骨牌号覆盖左上角子棋盘if(dr=tc+s)/特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else/特殊方格不在此棋盘中/用t号L型骨牌覆盖左下角,boardtr+s-1tc+s=t;/覆盖本子棋盘中的其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);/用L型骨牌号覆盖左下角子棋盘if(dr=tr+s,复杂度分析T(n)=O(4k)渐进意义下的最优算法,67,2,2,2,1,1,4,4,4,1,5,5,5,例,chessBoard(0,0,0,1,4),68,2.7合并排序,基本思想:
将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。
MergeSort(inta,intleft,intright)if(leftright)/至少有2个元素inti=(left+right)/2;/取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制回数组a,复杂度分析T(n)=O(nlogn)渐进意义下的最优算法,69,A=;,;,;,;,;,;,;,;,;,;,;,;,;,;,ShowMerge_Sort()runningonthearray,Example,;,;,;,;,70,复杂度,最坏时间复杂度:
O(nlogn)平均时间复杂度:
O(nlogn)辅助空间:
O(n)稳定性:
稳定,思考题:
给定有序表A1:
n,修改合并排序算法,求出该有序表的逆序对数。
71,2.8快速排序,在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。
qSort(intp,intr)if(pr)intq=partition(p,r);/以ap为基准元素将ap:
r划分成3段ap:
q-1,aq和aq+1:
r,使得ap:
q-1中任何元素小于等于aq,aq+1:
r中任何元素大于aq。
下标q在划分过程中确定。
qSort(p,q-1);/对左半段排序qSort(q+1,r);/对右半段排序,快速排序是对气泡排序的一种改进方法它是由C.A.R.Hoare于1962年提出的,72,函数partition的代码,partition(intp,intr)inti=p;intj=r+1;intx=ap;/将x的元素交换到右边区域while(true)while(a+ix);if(i=j)break;swap(a,i,j);ap=aj;aj=x;returnj;,例用快速排序法将6,7,5,2,5,8排序,73,randomizedPartition(intp,intr)inti=random(p,r);swap(a,i,p);returnpartition(p,r);,快速排序的复杂度,快速排序算法的性能取决于划分的对称性。
通过修改算法partition,可以设计出采用随机选择策略的快速排序算法。
在快速排序算法的每一步中,当数组还没有被划分时,可以在ap:
r中随机选出一个元素作为划分基准,这样可以使划分基准的选择是随机的,从而可以期望划分是较对称的。
最坏时间复杂度:
O(n2)平均时间复杂度:
O(nlogn)稳定性:
不稳定,74,快速排序时间复杂度的分析,最坏情况?
分割总是最不平衡最好情况?
每次将数组对半分割最可能情况?
介于上述两者之间,75,快速排序的平均复杂度,为简单起见,假定:
输入数据互不相等各种分割(0:
n-1,1:
n-2,2:
n-3,n-1:
0)出现的概率相等(1/n),设平均复杂度为T(n),则:
76,第二归纳法,77,ThusT(n)=O(nlgn),78,下面证明,79,80,各种排序算法的特点,归并排序使用分治思想时间复杂度O(nlgn)非就地排序,快速排序采用分治思想平均复杂度为O(nlgn)不稳定,81,排序算法的下界多大?
目前为止讨论
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 PPT 课件