算法设计与分析彭小刚--第1章算法引论.ppt

 算法设计与分析 教师：彭小刚 教师邮箱：drpengxg@126.com 登陆 选择学生，再注册自己的信息以便教学管理。 教学内容 第1章中介绍了算法的基本概念，接着对算法的计算复杂性和算法的描述作了简要的阐述。然后围绕设计算法常用的基本设计策略组织了第2章至第7章的内容 第2章介绍递归与分治策略，这是设计有效算法最常用策略，必须掌握的方法。 递归 分治的基本思想 二分有哪些信誉好的足球投注网站技术 大整数的乘法 Strassen矩阵乘法 合并排序 第3章介绍动态规划算法，以具体实例详述动态规划算法的设计思想、适用性以及算法的设计要点。 最短路径问题 最优性原理 矩阵连乘 0 /1 背包问题 可靠性设计 第4章介绍贪心算法，这也是一种重要的算法设计策略，它与动态规划算法的设计思想有一定的联系，但其效率更高。按贪心算法设计出的许多算法能产生最优解。其中有许多典型问题和典型算法可供学习和使用。 贪心算法的基本要素 背包问题 有限期的计算机作业调度 单源最短路径 第5章 回溯法 回溯法的算法框架 批处理作业调度 N后问题 背包问题 第6章 分支限界法 分支限界法的基本思想 单源最短路径问题 0 /1 背包问题 旅行商问题 第7 章简单介绍了NP完全性理论和解NP难问题的近似算法，这是当前计算机算法领域的热门研究课题，具有很高的实用价值 基本概念 一些典型的NP完全问题 近似算法及实例 教学进度 第1 章 算法引论 2 学时； 第2章 递归与分治策略 6 学时； 第3章 动态规划 2 学时； 第4章 贪心算法 6 学时； 第5章 回溯法 6 学时； 第6章 分支限界法 6学时； 第7 章 NP完全性理论简介 2学时； 评分方式 作业及实验 40％ 课堂表现 10％ 测验 50％ Presentation 酌情加分 迟交作业，酌情扣分 抄袭作弊，将导致记零分处理以及纪律处分 ！！！ 第1章 算法引论 1.1 算法与程序 1.2 算法复杂性分析 1.1 算法与程序 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 算法的描述 一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。 一般而言，描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。 从易于上机验证算法和提高实际程序设计能力考虑，采用C语言描述算法。 算法的正确性 若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。??? 一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案，一般只考虑正确的算法 算法分析 评价算法好坏的标准　　求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？??? 选用的算法首先应该是正确的。此外，主要考虑如下三点：① 执行算法所耗费的时间；② 执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③ 算法应易于理解，易于编码，易于调试等等 算法性能选择 　　一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：① 若该程序使用次数较少，则力求算法简明易懂；② 对于反复多次使用的程序，应尽可能选用快速的算法；③ 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。 1.2 算法复杂性分析 如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中） 1.4 算法时间复杂性 例： 有哪些信誉好的足球投注网站问题 渐近复杂性：对于T(N)，如果存在 ,使得 ,则 为T(N)的渐近性态。 Example：page 3 渐近记号: O, ?,?，o 算法复杂性在渐近意义下的阶：定义1 运算规则 根据O的定义，容易证明它有如下运算规则： (1)O(f)+O(g)=O(max(f,g))； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)；