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

预计进度安排 学习安排 成绩评定： 小论文：结合研究工作，50% 期末笔试：50% 证明(只证明第一种情况) (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)) 求职应注意的礼仪 求职时最礼貌的修饰是淡妆 面试时最关键的神情是郑重 无论站还是坐，不能摇动和抖动 对话时目光不能游弋不定 要控制小动作 不要为掩饰紧张情绪而散淡 最优雅的礼仪修养是体现自然 以一种修养面对两种结果 必须首先学会面对的一种结果----被拒绝 仍然感谢这次机会，因为被拒绝是面试后的两种结果之一。 被拒绝是招聘单位对我们综合考虑的结果，因为我们最关心的是自己什么地方与用人要求不一致，而不仅仅是面试中的表现。 不要欺骗自己，说“我本来就不想去”等等。 认真考虑是否有必要再做努力。 必须学会欣然面对的一种结果----被接纳 以具体的形式感谢招聘单位的接纳，如邮件、短信 考虑怎样使自己的知识能力更适应工作需要 把走进工作岗位当作职业生涯的重要的第一步，认真思考如何为以后的发展开好头。 Thank you * * * * * * * * * * * 多项式时间的算法 * 多项式时间的算法 时间复杂度函数为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 n2 10－4 4*10－4 9*10－4 16*10－4 25*10－4 36*10－4 n3 10－3 8*10－3 27*10－3 64*10－3 125*10－3 216*10－3 n5 10－1 3.2 24.3 1.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 世纪 * 时间复杂度函数 1小时可解的问题实例的最大规模 计算机 快100倍的计算机 快1000倍的计算机 n N1 100 N1 1000 N1 n2 N2 10 N2 31.6 N2 n3 N3 4.64 N3 10 N3 n5 N4 2.5 N4 3.98 N4 2n N5 N5 + 6.64 N5 + 9.97 3n N6 N6 + 4.19 N6 + 6.29 多项式函数与指数函数 * 问题的复杂度分析 多项式时间可解的问题与难解的问题 多项式时间可解的问题 P 存在着解P 的多项式时间的算法 难解的问题P 不存在解P 的多项式时间的算法 实际上可计算的问题 多项式时间可解的问题 * 不同复杂性类的基本层次结构 * 计 算 复 杂 性 类 的 谱 系 * 算法及计算复杂性理论的拓广 算法 概率算法 近似算法 在线算法 计算复杂性 概率Turing机与概率复杂性 近似解的复杂性 参数复杂性 * * * * * * * * * * * * * * * * * * * * * * * 算法分析与计算复杂性理论 * 课程简介 课程名称 算法分析与计算复杂性理论 Analysis of Algorithms and Theory of Computational Complexity 基本目的 掌握组合算法设计的基本技术 掌握算法分析的基本方法 掌握计算复杂性理论的基本概念 学习应用算法理论处理实际问题 * 课程内容 顺序算法设计的基本技术 分治策略 动态规划 回溯算法 贪心法 概率算法 顺序算法分析的基本方法 评价算法的标准 算法复杂性的估计 问题复杂性的下界 算法分析的实例 计算复杂性理论 Turing机 计算复杂性的概念 NP完全性理论及其应用 NP完全理论的拓广 1 小结 16 6 算法分析技术 8 2 NP完全理论的拓广 15 3 概率算法 7 2 NP完全理论应用 14 4 贪心法 6 5 NP完