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

1,算法分析与计算复杂性理论,2,课程简介,课程名称算法分析与计算复杂性理论AnalysisofAlgorithmsandTheoryofComputationalComplexity基本目的掌握组合算法设计的基本技术掌握算法分析的基本方法掌握计算复杂性理论的基本概念学习应用算法理论处理实际问题,3,课程内容,顺序算法设计的基本技术分治策略动态规划回溯算法贪心法概率算法顺序算法分析的基本方法评价算法的标准算法复杂性的估计问题复杂性的下界算法分析的实例计算复杂性理论Turing机计算复杂性的概念NP完全性理论及其应用NP完全理论的拓广,预计进度安排,5,教材与参考书,1.AlgorithmDesign,JonKleinberg,EvaTardos,Addison-Wesley,清华大学出版社影印版，2006.2.IntroductiontoAlgorithms（SecondEdtion）,ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,TheMITPress2001.高教出版社影印版，2002.3.计算机和难解性:NP完全性理论导引,M.R.加里,D.S.约翰逊,张立昂等译，科学出版社,1987.*4.计算复杂性导论，堵丁柱，葛可一，王洁，高教出版社2002.*5.LimitstoParallelComputation:P-CompletenessTheory,RaymondGreenlaw,H.JamesHoover,WalterL.Ruzzo,OxfordUniversityPress,1995.,学习安排,成绩评定：小论文：结合研究工作，50%期末笔试：50%,7,引言:理论上的可计算与现实上的可计算,算法研究的重要性理论上的可计算可计算性理论现实上的可计算计算复杂性理论,8,投资问题,问题：m元钱，投资给n个项目，效益函数fi(x)，表示第i个项目投入x元钱的效益，i=1,2,n.如何分配每个项目的钱数使得总效益最大？,采用什么算法？效率怎样？,令xi是第i个项目的钱数,9,蛮力算法的代价,Stirling公式：非负整数解的个数估计：蛮力算法穷举法代价太大能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术,10,T(n)=2T(n1)+1，T(1)=1，,ABC,思考：是否存在更好的解法？Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.其他变种：奇偶盘号分别放置,解得T(n)=2n1,1秒移1个，64个盘子要多少时间？（5000亿年）,Hanoi塔问题,11,其他问题,搜索问题输入：排好序的数组L，x输出：x是否在L中？如果在输出它的下标排序问题输入：n个数输出：按递增顺序排好的n个数选择问题输入：n个数的集合S，正整数k（1kn)输出：S中第k小的数需要：现有的算法中哪个算法最好？是否存在更有效的算法？,12,Algorithm+DataStructure=Programming,好的算法提高求解问题的效率节省存储空间需要解决的问题问题寻找求解算法算法设计技术算法算法的评价算法分析技术算法类问题复杂度的评价问题复杂性分析问题类能够求解的边界计算复杂性理论,13,算法研究的重要性,算法设计与分析技术在计算机科学与技术领域有着重要的应用背景算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域1966-2005期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖计算复杂性理论的核心课题“P=NP?”是本世纪7个最重要的数学问题之一通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用,14,理论上的可计算：可计算性理论,研究目标确定什么问题是可计算的，即存在求解算法合理的计算模型已有的：递归函数、Turing机、演算、Post系统等条件：计算一个函数只要有限条指令每条指令可以由模型中的有限个计算步骤完成指令执行的过程是确定的核心论题：Church-Turing论题如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的可计算性是不依赖于计算模型的客观性质,15,算法至少具有指数时间：理论上可计算难解的多项式时间的算法：现实上可计算多项式时间可解的对数多项式时间的算法：高度并行可解的,理论上与现实上的可计算性,16,计算复杂性理论,内容算法复杂度算法所使用的时间、空间的估计问题复杂度估计问题的难度术语和概念问题算法算法的时间复杂度函数的阶多项式时间的算法与指数时间的算法问题的复杂度分析,17,例1货郎担问题问题：有穷个城市的集合C=c1,c2,cm,正整数d(ci,cj)=d(cj,ci),1i0andAikey5.doAi+1Ai6.ii17.Ai+1key,22,算法的时间复杂度,最坏情况下的时间复杂度算法求解输入规模为n的实例所需要的最长时间W(n)平均情况下的时间复杂度算法求解输入规模为n的实例所需要的平均时间A(n)复杂度表示针对问题选择基本运算将基本运算次数表示为输入规模的函数,23,实例,搜索问题输入：非降顺序排列的数组L，元素数为n；数x输出：j.若x在L中，j是x首次出现的序标；否则j0算法顺序搜索假设x在L中的概率为px在L中不同位置是等概分布的，则,24,函数渐近的界,设f和g是定义域为自然数集N上的函数(1)f(n)=O(g(n)若存在正数c和n0使得对一切nn0有0f(n)cg(n)(2)f(n)=(g(n)若存在正数c和n0使得对一切nn0有0cg(n)f(n)(3)f(n)=o(g(n)对所有正数c1存在n0使得对一切nn0有0f(n)cg(n)(4)f(n)=(g(n).对所有正数c1存在n0使得对一切nn0有0cg(n)0，那么f(n)=(g(n).(2)如果，那么f(n)=o(g(n).(3)如果,那么f(n)=(g(n).,证明(只证明第一种情况),(1)根据极限定义，对于给定的正数=c/2,存在某个n0，只要nn0，就有对所有的nn0，f(n)2cg(n).从而推出f(n)=O(g(n)对所有的nn0，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,基本函数类,阶的高低至少指数级：2n,3n,n!,多项式级：n,n2,nlogn,n1/2,对数多项式级：logn,log2n,29,例题,例1设，证明f(n)=(n2).,根据定理1.1有f(n)=(n2).,30,例题,例2PrimalityTest(n)（素数检测）输入：n,n为大于2的奇整数输出：true或者false1s2forj2tos3ifj整除n4thenreturnfalse5returntrue假设计算可以在O(1)时间完成，可以写O(),不能写()，因为所需的测试次数小于等于之,31,多项式时间的算法,多项式时间的算法时间复杂度函数为O(p(n)的算法，其中p(n)是n的多项式不是多项式时间的算法不存在多项式p(n)使得该算法的时间复杂度为O(p(n)包含指数时间甚至更高阶的算法,多项式函数与指数函数,33,多项式函数与指数函数,34,问题的复杂度分析,多项式时间可