算法分析与计算复杂性理论幻灯片.ppt

算法分析与计算复杂算法分析与计算复杂性理论性理论第1页，共37页，编辑于2022年，星期一2课程简介课程简介p 课程名称课程名称 算法分析与计算复杂性理论算法分析与计算复杂性理论 Analysis of Algorithms and Theory of Computational Complexity p基本目的基本目的n掌握组合算法设计的基本技术掌握组合算法设计的基本技术n掌握算法分析的基本方法掌握算法分析的基本方法n掌握计算复杂性理论的基本概念掌握计算复杂性理论的基本概念n学习应用算法理论处理实际问题学习应用算法理论处理实际问题第2页，共37页，编辑于2022年，星期一3课程内容课程内容p顺序算法顺序算法设计设计的基本技术的基本技术 分治策略分治策略 动态规划动态规划 回溯算法回溯算法 贪心法贪心法 概率算法概率算法p顺序算法顺序算法分析分析的基本方法的基本方法 评价算法的标准评价算法的标准 算法复杂性的估计算法复杂性的估计 问题复杂性的下界问题复杂性的下界 算法分析的实例算法分析的实例p计算计算复杂性复杂性理论理论 Turing机机 计算复杂性的概念计算复杂性的概念 NP完全性理论及其应用完全性理论及其应用 NP完全理论的拓广完全理论的拓广 第3页，共37页，编辑于2022年，星期一预计进度安排预计进度安排内容内容学学时时内容内容学学时时1前言前言19Turing机机22数学基数学基础础210计计算复算复杂杂性理性理论论23分治策略分治策略411NP完全性理完全性理论论24动态规动态规划划412Cook定理定理15回溯与分支估界回溯与分支估界413NP完全性完全性证证明明56贪贪心法心法414NP完全理完全理论应论应用用27概率算法概率算法315NP完全理完全理论论的拓广的拓广 28算法分析技算法分析技术术616小小结结1第4页，共37页，编辑于2022年，星期一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.第5页，共37页，编辑于2022年，星期一学习安排学习安排p成绩评定：成绩评定：n小论文：结合研究工作，小论文：结合研究工作，50%n期末笔试：期末笔试：50%第6页，共37页，编辑于2022年，星期一7引言引言:理论上的可计算与现实上的可计算理论上的可计算与现实上的可计算 p算法研究的重要性算法研究的重要性p理论上的可计算理论上的可计算 可计算性理论可计算性理论 p现实上的可计算现实上的可计算 计算复杂性理论计算复杂性理论 第7页，共37页，编辑于2022年，星期一8投资问题投资问题问题：问题：m元钱，投资给元钱，投资给n个项目，效益函数个项目，效益函数 fi(x)，表示第，表示第 i 个项目个项目投入投入x元钱的效益，元钱的效益，i=1,2,n.如何分配每个项目的钱数使如何分配每个项目的钱数使得总效益最大？得总效益最大？采用什么算法？效率怎样？采用什么算法？效率怎样？令令xi 是第是第 i 个项目的钱数个项目的钱数第8页，共37页，编辑于2022年，星期一9蛮力算法的代价蛮力算法的代价Stirling公式：公式：非负整数解非负整数解 的的个数估计：个数估计：蛮力算法蛮力算法穷举法代价太大穷举法代价太大能否利用解之间的依赖关系找到更好的算法？能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术结论：需要算法设计技术 第9页，共37页，编辑于2022年，星期一10 T(n)=2 T(n 1)+1，T(1)=1，A B C思考：是否存在更好的解法？思考：是否存在更好的解法？Reve难题：难题：Hanoi塔变种，柱数增加，允许盘子相等塔变种，柱数增加，允许盘子相等.其他变种其他变种：奇偶盘号分别放置奇偶盘号分别放置解得解得 T(n)=2n 1 1秒移秒移1个，个，64个盘子要多少时间？（个盘子要多少时间？（5000亿年）亿年）Hanoi塔问题塔问题第10页，共37页，编辑于2022年，星期一11其他问题其他问题搜索问题搜索问题 输入：排好序的数组输入：排好序的数组 L，x 输出：输出：x 是否在是否在 L 中？如果在输出它的下标中？如果在输出它的下标排序问题排序问题 输入：输入：n个数个数 输出：按递增顺序排好的输出：按递增顺序排好的n个数个数选择问题选择问题 输入：输入：n个数的集合个数的集合S，正整数，正整数k（1 k n)输出：输出：S中第中第 k 小的数小的数需要：需要：现有的算法中哪个算法最好？现有的算法中哪个算法最好？是否存在更有效的算法？是否存在更有效的算法？第11页，共37页，编辑于2022年，星期一12Algorithm+Data Structure=Programmingp好的算法好的算法n提高求解问题的效率提高求解问题的效率n节省存储空间节省存储空间 p需要解决的问题需要解决的问题n问题问题寻找求解寻找求解算法算法 算法设计技术算法设计技术n算法算法算法的评价算法的评价 算法分析技术算法分析技术n算法类算法类问题复杂度的评价问题复杂度的评价 问题复杂性分析问题复杂性分析n问题类问题类能够求解的边界能够求解的边界 计算复杂性理论计算复杂性理论 第12页，共37页，编辑于2022年，星期一13算法研究的重要性算法研究的重要性p算法设计与分析技术在计算机科学与技术领域有着重要的应用背算法设计与分析技术在计算机科学与技术领域有着重要的应用背景景 p算法设计分析与计算复杂性理论的研究是计算机科学技术的算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域核心研究领域 n1966-2005期间，期间，Turing奖获奖奖获奖50人，其中人，其中10人以算法人以算法设计，设计，7人以计算理论、自动机和复杂性研究领域的杰人以计算理论、自动机和复杂性研究领域的杰出贡献获奖出贡献获奖n计算复杂性理论的核心课题计算复杂性理论的核心课题“P=NP?”是本世纪是本世纪7个最个最重要的数学问题之一重要的数学问题之一p通过算法设计与分析课程的训练对提高学生的素质和分析问通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用题解决问题的能力有着重要的作用第13页，共37页，编辑于2022年，星期一14理论上的可计算：可计算性理论理论上的可计算：可计算性理论p研究目标研究目标 确定什么问题是可计算的，即存在求解算法确定什么问题是可计算的，即存在求解算法p合理的计算模型合理的计算模型 已有的：递归函数、已有的：递归函数、Turing机、机、演算、演算、Post系统等系统等 条件：计算一个函数只要有限条指令条件：计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的指令执行的过程是确定的p核心论题：核心论题：Church-Turing论题论题 如果一个函数在某个合理的计算模型上可计算，那么它在如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的机上也是可计算的 p可计算性是不依赖于计算模型的客观性质可计算性是不依赖于计算模型的客观性质 第14页，共37页，编辑于2022年，星期一15算法至少具有指数时间：理论上可计算算法至少具有指数时间：理论上可计算难解的难解的多项式时间的算法：现实上可计算多项式时间的算法：现实上可计算多项式时间可解的多项式时间可解的对数多项式时间的算法：高度并行可解的对数多项式时间的算法：高度并行可解的理论上可计算理论上可计算 理论上理论上不可计算不可计算现实可计算现实可计算高度并行高度并行 可计算可计算理论上与现实上的可计算性理论上与现实上的可计算性第15页，共37页，编辑于2022年，星期一16计算复杂性理论计算复杂性理论内容内容p算法复杂度算法复杂度算法所使用的时间、空间的估计算法所使用的时间、空间的估计p问题复杂度问题复杂度估计问题的难度估计问题的难度术语和概念术语和概念p问题问题p算法算法p算法的时间复杂度算法的时间复杂度p函数的阶函数的阶p多项式时间的算法与指数时间的算法多项式时间的算法与指数时间的算法p问题的复杂度分析问题的复杂度分析第16页，共37页，编辑于2022年，星期一17例例1 1 货货郎担郎担问题问题问题问题：有：有穷穷个城市的集合个城市的集合C=c1,c2,cm,正整数正整数d(ci,cj)=d(cj,ci),1 i 0 and Ai key5.do Ai+1 Ai6.i i 17.Ai+1 key 第21页，共37页，编辑于2022年，星期一22算法的时间复杂度算法的时间复杂度p最坏情况下的时间复杂度最坏情况下的时间复杂度 算法求解输入规模为算法求解输入规模为n的实例所需要的最长时间的实例所需要的最长时间W(n)p平均情况下的时间复杂度平均情况下的时间复杂度 算法算法求解输入规模为求解输入规模为n的实例所需要的平均时间的实例所需要的平均时间A(n)p复杂度表示复杂度表示 针对问题选择基本运算针对问题选择基本运算 将基本运算次数表示为输入规模的函数将基本运算次数表示为输入规模的函数第22页，共37页，编辑于2022年，星期一23实例实例搜索问题搜索问题输入：非降顺序排列的数组输入：非降顺序排列的数组L，元素数为，元素数为n；数数x输出：输出：j.若若x在在L中，中，j 是是 x 首次出现的序标；否则首次出现的序标；否则 j 0算法算法 顺序搜索顺序搜索假设假设 x 在在 L 中的概率为中的概率为 p x 在在 L 中不同位置是等概分布的，则中不同位置是等概分布的，则第23页，共37页，编辑于2022年，星期一24函数渐近的界函数渐近的界设设 f 和和 g 是定义域为自然数集是定义域为自然数集 N上的函数上的函数(1)f(n)=O(g(n)若存在正数若存在正数c和和n0使得对一切使得对一切n n0有有0 f(n)cg(n)(2)f(n)=(g(n)若存在正数若存在正数c和和n0使得对一切使得对一切n n0有有0 cg(n)f(n)(3)f(n)=o(g(n)对所有正数对所有正数c1存在存在n0使得对一切使得对一切n n0有有0 f(n)cg(n)(4)f(n)=(g(n).对所有正数对所有正数c1存在存在n0使得对一切使得对一切n n0有有0 cg(n)0，那么，那么 f(n)=(g(n).(2)如果如果 ，那么，那么 f(n)=o(g(n).(3)如果如果 ,那么那么 f(n)=(g(n).第25页，共37页，编辑于2022年，星期一证明证明(只证明第一种情况只证明第一种情况)(1)根据极限定义，对于给定的正数根据极限定义，对于给定的正数=c/2,存在某个存在某个n0，只要，只要n n0，就有，就有对所有的对所有的n n0，f(n)2cg(n).从而推出从而推出 f(n)=O(g(n)对所有的对所有的n n0，f(n)(c/2)g(n)，从而推出，从而推出 f(n)=(g(n),于是于是 f(n)=(g(n)第26页，共37页，编辑于2022年，星期一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).函数渐近的界的基本性质函数渐近的界的基本性质第27页，共37页，编辑于2022年，星期一28基本函数类基本函数类 阶的高低阶的高低 至少指数级：至少指数级：2n,3n,n!,多项式级：多项式级：n,n2,nlogn,n1/2,对数多项式级：对数多项式级：logn,log2n,第28页，共37页，编辑于2022年，星期一例题例题29例例1 设设 ，证证明明 f(n)=(n2).根据定理根据定理1.1有有 f(n)=(n2).第29页，共37页，编辑于2022年，星期一30例题例题例例2 PrimalityTest(n)（素数（素数检测检测）输输入：入：n,n为为大于大于 2 的奇整数的奇整数输输出：出：true 或者或者false1s 2for j 2 to s3 if j 整除整除 n 4 then return false5return true假假设计设计算算 可以在可以在O(1)时间时间完成，可以写完成，可以写O(),不能写不能写()，因，因为为所需的所需的测试测试次数小于等于之次数小于等于之第30页，共37页，编辑于2022年，星期一多项式时间的算法多项式时间的算法31p多项式时间的算法多项式时间的算法 时间复杂度函数为时间复杂度函数为O(p(n)的算法，其中的算法，其中p(n)是是n的多项的多项式式p不是多项式时间的算法不是多项式时间的算法 不存在多项式不存在多项式 p(n)使得该算法的时间复杂度为使得该算法的时间复杂度为 O(p(n)包含指数时间甚至更高阶的算法包含指数时间甚至更高阶的算法第31页，共37页，编辑于2022年，星期一多项式函数与指数函数多项式函数与指数函数时间时间复复杂杂度函数度函数问题规问题规模模102030405060n1052*1053*1054*1055*1056*105n21044*1049*10416*10425*10436*104n31038*10327*10364*103125*103216*103n51013.224.31.7 分分5.2 分分13.0 分分2n.001 秒秒1.0 秒秒17.9 分分12.7 天天35.7 年年366 世世纪纪3n.059 秒秒58 分分6.5 年年3855 世世纪纪2*108 世世纪纪1.3*1013 世世纪纪第32页，共37页，编辑于2022年，星期一33 时间时间复复杂杂度函数度函数1小小时时可解的可解的问题实问题实例的最大例的最大规规模模计计算机算机快快100倍的倍的计计算机算机快快1000倍的倍的计计算机算机nN1100 N11000 N1n2N210 N231.6 N2n3N34.64 N310 N3n5N42.5 N43.98 N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29多项式函数与指数函数多项式函数与指数函数第33页，共37页，编辑于2022年，星期一34问题的复杂度分析问题的复杂度分析多多项项式式时间时间可解的可解的问题问题与与难难解的解的问题问题p多多项项式式时间时间可解的可解的问题问题 P 存在着解存在着解P 的多的多项项式式时间时间的算法的算法p难难解的解的问题问题P 不存在解不存在解P 的多的多项项式式时间时间的算法的算法p实际实际上可上可计计算的算的问题问题 多多项项式式时间时间可解的可解的问题问题第34页，共37页，编辑于2022年，星期一35不同复杂性类的基本层次结构不同复杂性类的基本层次结构第35页，共37页，编辑于2022年，星期一36计计算算复复杂杂性性类类的的谱谱系系第36页，共37页，编辑于2022年，星期一37算法及计算复杂性理论的拓广算法及计算复杂性理论的拓广p算法算法n概率算法概率算法n近似算法近似算法n在线算法在线算法p计算复杂性计算复杂性n概率概率Turing机与概率复杂性机与概率复杂性n近似解的复杂性近似解的复杂性n参数复杂性参数复杂性第37页，共37页，编辑于2022年，星期一