算法分析与计算复杂性理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,算法分析与,计算复杂性理论,2,课程简介,课程名称,算法分析与计算复杂性理论,Analysis of Algorithms and,Theory of Computational Complexity,基本目的,掌握组合算法设计的基本技术,掌握算法分析的基本方法,掌握计算复杂性理论的基本概念,学习应用算法理论处理实际问题,3,课程内容,顺序算法,设计,的基本技术,分治策略 动态规划,回溯算法 贪心法,概率算法,顺序算法,分析,的基本方法,评价算法的标准,算法复杂性的估计,问题复杂性的下界 算法分析的实例,计算,复杂性,理论,Turing,机,计算复杂性的概念,NP,完全性理论及其应用,NP,完全理论的拓广,预计进度安排,内容,学时,内容,学时,1,前言,1,9,Turing,机,2,2,数学基础,2,10,计算复杂性理论,2,3,分治策略,4,11,NP,完全性理论,2,4,动态规划,4,12,Cook,定理,1,5,回溯与分支估界,4,13,NP,完全性证明,5,6,贪心法,4,14,NP,完全理论应用,2,7,概率算法,3,15,NP,完全理论的拓广,2,8,算法分析技术,6,16,小结,1,5,教材与参考书,1.Algorithm Design,Jon Kleinberg,Eva Tardos,Addison-Wesley,清华大学出版社影印版,，,2006.,2.Introduction to Algorithms,（,Second Edtion,）,Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,The MIT Press 2001.,高教出版社影印版，,2002.,3.,计算机和难解性,:,NP,完全性理论导引,M.R.,加里,D.S.,约翰逊,张立昂等译，科学出版社,1987.,*4.,计算复杂性导论，堵丁柱，葛可一，王洁，高教出版社,2002.,*5.Limits to Parallel Computation:P-Completeness Theory,Raymond Greenlaw,H.James Hoover,Walter L.Ruzzo,Oxford University Press,1995.,学习安排,成绩评定：,小论文：结合研究工作，,50,%,期末笔试：,50,%,7,引言,:,理论上的可计算与现实上的可计算,算法研究的重要性,理论上的可计算,可计算性理论,现实上的可计算,计算复杂性理论,8,投资问题,问题：,m,元钱，投资给,n,个项目，效益函数,f,i,(,x,),，表示第,i,个项目,投入,x,元钱的效益，,i,=1,2,n.,如何分配每个项目的钱数使,得总效益最大？,采用什么算法？效率怎样？,令,x,i,是第,i,个项目的钱数,9,蛮力算法的代价,Stirling,公式：,非负整数解,的,个数估计：,蛮力算法,穷举法代价太大,能否利用解之间的依赖关系找到更好的算法？,结论：需要算法设计技术,10,T,(,n,)=2,T,(,n,1)+1,，,T,(1)=1,，,A B C,思考：是否存在更好的解法？,Reve,难题：,Hanoi,塔变种，柱数增加，允许盘子相等,.,其他变种,：,奇偶盘号分别放置,解得,T,(,n,)=2,n,1,1,秒移,1,个，,64,个盘子要多少时间？（,5000,亿年）,Hanoi,塔问题,11,其他问题,搜索问题,输入：排好序的数组,L,，,x,输出：,x,是否在,L,中？如果在输出它的下标,排序问题,输入：,n,个数,输出：按递增顺序排好的,n,个数,选择问题,输入：,n,个数的集合,S,，正整数,k,（,1,k,n,),输出：,S,中第,k,小的数,需要：,现有的算法中哪个算法最好？,是否存在更有效的算法？,12,Algorithm+Data Structure=Programming,好的算法,提高求解问题的效率,节省存储空间,需要解决的问题,问题,寻找求解,算法,算法设计技术,算法,算法的评价,算法分析技术,算法类,问题复杂度的评价,问题复杂性分析,问题类能够求解的边界,计算复杂性理论,13,算法研究的重要性,算法设计与分析技术在计算机科学与技术领域有着重要的应用背景,算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域,1966-2005,期间，,Turing,奖获奖,50,人，其中,10,人以算法设计，,7,人以计算理论、自动机和复杂性研究领域的杰出贡献获奖,计算复杂性理论的核心课题“,P=NP?”,是本世纪,7,个最重要的数学问题之一,通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用,14,理论上的可计算：可计算性理论,研究目标,确定什么问题是可计算的，即存在求解算法,合理的计算模型,已有的：递归函数、,Turing,机、,演算、,Post,系统等,条件：计算一个函数只要有限条指令,每条指令可以由模型中的有限个计算步骤完成,指令执行的过程是确定的,核心论题：,Church-Turing,论题,如果一个函数在某个合理的计算模型上可计算，那么它在,Turing,机上也是可计算的,可计算性是不依赖于计算模型的客观性质,15,算法至少具有指数时间：理论上可计算,难解的,多项式时间的算法：现实上可计算,多项式时间可解的,对数多项式时间的算法：高度并行可解的,理论上可计算,理论上,不可计算,现实可计算,高度并行,可计算,理论上与现实上的可计算性,16,计算复杂性理论,内容,算法复杂度,算法所使用的时间、空间的估计,问题复杂度,估计问题的难度,术语和概念,问题,算法,算法的时间复杂度,函数的阶,多项式时间的算法与指数时间的算法,问题的复杂度分析,17,例,1,货郎担问题,问题：有穷个城市的集合,C,=,c,1,c,2,c,m,正整数,d,(,c,i,c,j,)=,d,(,c,j,c,i,),1,i,0 and,A,i,key,5.do,A,i,+1,A,i,6.,i,i,1,7.,A,i,+1,key,22,算法的时间复杂度,最坏情况下的时间复杂度,算法求解输入规模为,n,的实例所需要的最长时间,W,(,n,),平均情况下的时间复杂度,算法,求解输入规模为,n,的实例所需要的平均时间,A,(,n,),复杂度表示,针对问题选择基本运算,将基本运算次数表示为输入规模的函数,23,实例,搜索问题,输入：非降顺序排列的数组,L,，元素数为,n,；数,x,输出：,j,.,若,x,在,L,中，,j,是,x,首次出现的序标；否则,j,0,算法 顺序搜索,假设,x,在,L,中的概率为,p,x,在,L,中不同位置是等概分布的，则,24,函数渐近的界,设,f,和,g,是定义域为自然数集,N,上的函数,(1),f,(,n,)=,O,(,g,(,n,),若存在正数,c,和,n,0,使得对一切,n,n,0,有,0,f,(,n,),cg,(,n,),(2),f,(,n,)=,(,g,(,n,),若存在正数,c,和,n,0,使得对一切,n,n,0,有,0,cg,(,n,),f,(,n,),(3),f,(,n,)=,o,(,g,(,n,),对所有正数,c,1,存在,n,0,使得对一切,n,n,0,有,0,f,(,n,),cg,(,n,),(4),f,(,n,)=,(,g,(,n,).,对所有正数,c,1,存在,n,0,使得对一切,n,n,0,有,0,cg,(,n,)0,，那么,f,(,n,)=,(,g,(,n,).,(2),如果 ，那么,f,(,n,)=,o,(,g,(,n,).,(3),如果,那么,f,(,n,)=,(,g,(,n,).,证明,(,只证明第一种情况,),(1),根据极限定义，对于给定的正数,=,c,/2,存在某个,n,0,，只要,n,n,0,，就有,对所有的,n,n,0,，,f,(,n,),2,cg,(,n,).,从而推出,f,(,n,)=,O,(,g,(,n,),对所有的,n,n,0,，,f,(,n,),(,c,/2),g,(,n,),，从而推出,f,(,n,)=,(,g,(,n,),于是,f,(,n,)=,(,g,(,n,),27,定理,1.2,设,f,g,h,是定义域为自然数集合的函数，,(1),如果,f,=,O,(,g,),且,g,=,O,(,h,),，那么,f,=,O,(,h,).,(2),如果,f,=,(,g,),且,g,=,(,h,),，,那么,f,=,(,h,).,(3),如果,f,=,(,g,),和,g,=,(,h,),，,那么,f,=,(,h,).,定理,1.3,假设,f,和,g,是定义域为自然数集合的函数，若对某个其它的函数,h,我们有,f,=,O,(,h,),和,g,=,O,(,h,),，那么,f,+,g,=,O,(,h,).,推论,假设,f,和,g,是定义域为自然数集合的函数，且满足,g,=,O,(,f,),，那么,f,+,g,=,(,f,).,函数渐近的界的基本性质,28,基本函数类,阶的高低,至少指数级：,2,n,3,n,n,!,多项式级：,n,n,2,n,log,n,n,1/2,对数多项式级：,log,n,log,2,n,例题,29,例,1,设,，证明,f,(,n,)=,(,n,2,).,根据定理,1.1,有,f,(,n,)=,(,n,2,).,30,例题,例,2,PrimalityTest(,n,),（素数检测）,输入：,n,n,为大于,2,的奇整数,输出：,true,或者,false,1,s,2,for,j,2 to,s,3,if,j,整除,n,4,then return false,5,return true,假设计算 可以在,O,(1),时间完成，可以写,O,(),不能写,(),，因为,所需的测试次数小于等于之,多项式时间的算法,31,多项式时间的算法,时间复杂度函数为,O,(,p,(,n,),的算法，其中,p,(,n,),是,n,的多项式,不是多项式时间的算法,不存在多项式,p,(,n,),使得该算法的时间复杂度为,O,(,p,(,n,),包含指数时间甚至更高阶的算法,多项式函数与指数函数,时间复杂,度函数,问题规模,10,20,30,40,50,60,n,10,5,2*10,5,3*10,5,4*10,5,5*10,5,6*10,5,n,2,10,4,4*10,4,9*10,4,16*10,4,25*10,4,36*10,4,n,3,10,3,8*10,3,27*10,3,64*10,3,125*10,3,216*10,3,n,5,10,1,3.2,24.3,1.7,分,5.2,分,13.0,分,2,n,.001,秒,1.0,秒,17.9,分,12.7,天,35.7,年,366,世纪,3,n,.059,秒,58,分,6.5,年,3855,世纪,2*10,8,世纪,1.3*10,13,世纪,33,时间复杂度函数,1,小时可解的问题实例的最大规模,计算机,快,100,倍的计算机,快,1000,倍的计算机,n,N,1,100 N,1,1000 N,1,n,2,N,2,10 N,2,31.6 N,2,n,3,N,3,4.64 N,3,10 N,3,n,5,N,4,2.5 N,4,3.98 N,4,2,n,N,5,N,5,+6.64,N,5,+9.97,3,n,N,6,N,6,+4.19,N,6,+6.29,多项式函数与指数函数,34,问题的复杂度分析,多项式时间可解的问题与难解的问题,多项式时间可解的问题,P,存在着解,P,的多项式时间的算法,难解的问题,P,不存在解,P,的多项式时间的算法,实际上可计算的问题,多项式时间可解的问题,35,不同复杂性类的基本层次结构,36,计,算,复,杂,性,类,的,谱,系,37,算法及计算复杂性理论的拓广,算