《算法分析与计算复杂性理论》由会员分享，可在线阅读，更多相关《算法分析与计算复杂性理论（37页珍藏版）》请在金锄头文库上搜索。
1、1,算法分析与 计算复杂性理论,2,课程简介,课程名称算法分析与计算复杂性理论Analysis of Algorithms and Theory of Computational Complexity 基本目的 掌握组合算法设计的基本技术 掌握算法分析的基本方法 掌握计算复杂性理论的基本概念 学习应用算法理论处理实际问题,3,课程内容,顺序算法设计的基本技术分治策略 动态规划回溯算法 贪心法概率算法 顺序算法分析的基本方法评价算法的标准 算法复杂性的估计问题复杂性的下界 算法分析的实例 计算复杂性理论Turing机计算复杂性的概念NP完全性理论及其应用NP完全理论的拓广,预计进度安排,5,教材
2、与参考书,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. 计算复杂性导论，堵
3、丁柱，葛可一，王洁，高教出版社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个项目，效益函数 fi(x)，表示第 i 个
4、项目 投入x元钱的效益，i=1,2,n. 如何分配每个项目的钱数使 得总效益最大？,采用什么算法？效率怎样？,令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,其他问
5、题,搜索问题输入：排好序的数组 L，x输出：x 是否在 L 中？如果在输出它的下标 排序问题输入：n个数输出：按递增顺序排好的n个数 选择问题输入：n个数的集合S，正整数k（1kn)输出：S中第 k 小的数 需要：现有的算法中哪个算法最好？是否存在更有效的算法？,12,Algorithm + Data Structure = Programming,好的算法 提高求解问题的效率 节省存储空间 需要解决的问题 问题寻找求解算法 算法设计技术 算法算法的评价 算法分析技术 算法类问题复杂度的评价 问题复杂性分析 问题类能够求解的边界 计算复杂性理论,13,算法研究的重要性,算法设计与分析技术在计算
6、机科学与技术领域有着重要的应用背景 算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域 1966-2005期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖 计算复杂性理论的核心课题 “P=NP?” 是本世纪7个最重要的数学问题之一 通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用,14,理论上的可计算：可计算性理论,研究目标确定什么问题是可计算的，即存在求解算法 合理的计算模型已有的：递归函数、Turing机、演算、Post系统等条件：计算一个函数只要有限条指令每条指令可以由模型中的有限个
7、计算步骤完成指令执行的过程是确定的 核心论题：Church-Turing论题如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的 可计算性是不依赖于计算模型的客观性质,15,算法至少具有指数时间：理论上可计算难解的 多项式时间的算法：现实上可计算多项式时间可解的 对数多项式时间的算法：高度并行可解的,理论上与现实上的可计算性,16,计算复杂性理论,内容 算法复杂度算法所使用的时间、空间的估计 问题复杂度估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析,17,例1 货郎担问题 问题：有穷个城市的集合C
8、 = c1, c2, , cm, 正整数d (ci, cj) = d (cj, ci), 1 i 0 and Ai key 5. do Ai+1 Ai 6. i i 1 7. Ai+1 key,22,算法的时间复杂度,最坏情况下的时间复杂度算法求解输入规模为n的实例所需要的最长时间W(n) 平均情况下的时间复杂度算法求解输入规模为n的实例所需要的平均时间A(n) 复杂度表示针对问题选择基本运算将基本运算次数表示为输入规模的函数,23,实例,搜索问题 输入：非降顺序排列的数组L，元素数为n； 数x 输出：j. 若x在L中，j 是 x 首次出现的序标；否则 j 0 算法 顺序搜索 假设 x 在 L
9、 中的概率为 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).
10、,证明(只证明第一种情况),(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是定义域为自然数集合
11、的函数，若对某个其它的函数 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,例题,例2 PrimalityTest(n) （素数检测） 输入：n, n为大于 2 的奇整数 输出：true 或者fal
12、se 1s 2for j 2 to s 3 if j 整除 n 4 then return false 5return true 假设计算 可以在O(1)时间完成，可以写O( ), 不能写( )，因为所需的测试次数小于等于之,多项式时间的算法,31,多项式时间的算法时间复杂度函数为O(p(n)的算法，其中p(n)是n的多项式 不是多项式时间的算法不存在多项式 p(n)使得该算法的时间复杂度为O(p(n) 包含指数时间甚至更高阶的算法,多项式函数与指数函数,33,多项式函数与指数函数,34,问题的复杂度分析,多项式时间可解的问题与难解的问题 多项式时间可解的问题 P存在着解P 的多项式时间的算法 难解的问题P不存在解P 的多项式时间的算法 实际上可计算的问题多项式时间可解的问题,35,不同复杂性类的基本层次结构,36,计 算 复 杂 性 类 的 谱 系,
