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

《算法分析与计算复杂性理论.ppt》由会员分享，可在线阅读，更多相关《算法分析与计算复杂性理论.ppt（37页珍藏版）》请在三一办公上搜索。

1、1,算法分析与计算复杂性理论,2,课程简介,课程名称 算法分析与计算复杂性理论 Analysis of Algorithms and Theory of Computational Complexity 基本目的掌握组合算法设计的基本技术掌握算法分析的基本方法掌握计算复杂性理论的基本概念学习应用算法理论处理实际问题,3,课程内容,顺序算法设计的基本技术 分治策略 动态规划 回溯算法 贪心法 概率算法顺序算法分析的基本方法 评价算法的标准 算法复杂性的估计 问题复杂性的下界 算法分析的实例计算复杂性理论 Turing机 计算复杂性的概念 NP完全性理论及其应用 NP完全理论的拓广,预计进度安排,

2、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.

3、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个项目，效益函数 fi(x)，表示第 i 个项目投入x元钱的效益，i=1,2,n.如何分配每个项目的钱数使得总效益最大

4、？,采用什么算法？效率怎样？,令xi 是第 i 个项目的钱数,9,蛮力算法的代价,Stirling公式：非负整数解 的个数估计：蛮力算法穷举法代价太大能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术,10,T(n)=2 T(n1)+1，T(1)=1，,A B C,思考：是否存在更好的解法？Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.其他变种：奇偶盘号分别放置,解得 T(n)=2n 1,1秒移1个，64个盘子要多少时间？（5000亿年）,Hanoi塔问题,11,其他问题,搜索问题 输入：排好序的数组 L，x 输出：x 是否在 L 中？如果在输出它的下标排序问题 输入：n

5、个数 输出：按递增顺序排好的n个数选择问题 输入：n个数的集合S，正整数k（1kn)输出：S中第 k 小的数需要：现有的算法中哪个算法最好？是否存在更有效的算法？,12,Algorithm+Data Structure=Programming,好的算法提高求解问题的效率节省存储空间 需要解决的问题问题寻找求解算法 算法设计技术算法算法的评价 算法分析技术算法类问题复杂度的评价 问题复杂性分析问题类能够求解的边界 计算复杂性理论,13,算法研究的重要性,算法设计与分析技术在计算机科学与技术领域有着重要的应用背景 算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域 1966-2005

6、期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖计算复杂性理论的核心课题“P=NP?”是本世纪7个最重要的数学问题之一通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用,14,理论上的可计算：可计算性理论,研究目标 确定什么问题是可计算的，即存在求解算法合理的计算模型 已有的：递归函数、Turing机、演算、Post系统等 条件：计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的核心论题：Church-Turing论题 如果一个函数在某个合理的计算模型上可计算，那

7、么它在Turing机上也是可计算的 可计算性是不依赖于计算模型的客观性质,15,算法至少具有指数时间：理论上可计算难解的多项式时间的算法：现实上可计算多项式时间可解的对数多项式时间的算法：高度并行可解的,理论上与现实上的可计算性,16,计算复杂性理论,内容算法复杂度算法所使用的时间、空间的估计问题复杂度估计问题的难度术语和概念问题算法算法的时间复杂度函数的阶多项式时间的算法与指数时间的算法问题的复杂度分析,17,例1 货郎担问题问题：有穷个城市的集合C=c1,c2,cm,正整数d(ci,cj)=d(cj,ci),1 i j m.解：使得 k1,k2,km是1,2,m 的置换且满足,问题,问题：

8、需要回答的一般性提问，通常含有若干参数 问题描述所包含的内容：对问题参数的一般性描述，解满足的条件问题的实例：对问题的参数的一组赋值,18,实例,C=c1,c2,c3,c4,d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9 d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=3,19,算法,非形式定义 有限条指令的集合 指令集确定了解决某个问题的运算或操作的序列 输入个数大于等于0 输出个数大于0形式定义 对所有的有效输入停机的Turing机算法 A 解问题 P 把问题P的任何实例作为算法A的输入，A能够在有限步 停机，并输出该实例的正确的解,20,算法的描述：伪码

9、,保持程序的主要结构类 C,Pascal赋值语句：分支语句：if then else循环语句：while,for，repeat.until 转向语句：goto调用注释：/允许使用自然语言常忽略数据结构、模块、异常处理等细节常忽略变量说明,21,伪码的例子：插入排序,算法 INSERTION-SORT(A)1.for j 2 to lengthA 2.do key Aj/将Aj插入排好序的序列 A1.j13.i j14.while i 0 and Ai key5.do Ai+1 Ai6.i i 17.Ai+1 key,22,算法的时间复杂度,最坏情况下的时间复杂度 算法求解输入规模为n的实例所需

10、要的最长时间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和n0使得对一切nn0有0f(n)cg(n)(2)f(n)=(g(n)若存在正数c和n0使得对一切nn0有0cg(n

11、)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)f(n)(5)f(n)=(g(n)f(n)=O(g(n)且 f(n)=(g(n)(6)O(1)表示常数函数,25,函数渐近的界的基本性质,定理1.1 设 f 和 g 是定义域为自然数集 N上的函数.(1)如果 存在，并且等于某个常数c0，那么 f(n)=(g(n).(2)如果，那么 f(n)=o(g(n).(3)如果,那么 f(n)=(g(n).,证明(只证明第一种情况),(1)根据极限定义，对于给定的正数=c/2,存

12、在某个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是定

13、义域为自然数集合的函数，且满足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,例题,例2 PrimalityTest(n)（素数检测）输入：n,n为大于 2 的奇整数输出：true 或者false1s 2for j 2 to s3 if j 整除 n 4 then return false5return true假设计算 可以在O(1)时间完成，可以写

14、O(),不能写()，因为所需的测试次数小于等于之,多项式时间的算法,31,多项式时间的算法 时间复杂度函数为O(p(n)的算法，其中p(n)是n的多项式不是多项式时间的算法 不存在多项式 p(n)使得该算法的时间复杂度为 O(p(n)包含指数时间甚至更高阶的算法,多项式函数与指数函数,33,多项式函数与指数函数,34,问题的复杂度分析,多项式时间可解的问题与难解的问题多项式时间可解的问题 P 存在着解P 的多项式时间的算法难解的问题P 不存在解P 的多项式时间的算法实际上可计算的问题 多项式时间可解的问题,35,不同复杂性类的基本层次结构,36,计算复杂性类的谱系,37,算法及计算复杂性理论的拓广,算法概率算法近似算法在线算法计算复杂性概率Turing机与概率复杂性近似解的复杂性参数复杂性,