数据结构第三章的.pdfVIP

什么是算法？ 第一章 绪论 • 算法是对解决问题的方法的一种精确描述。 1.1引言 1.2数据结构的有关基本概念； • 并非所有问题都有算法，有些问题经研究可行， 1.3算法及算法分析（算法评价） 则可能有相应算法；而有些问题经研究不可行， 1.4递归 则没有相应算法。 • 因此，算法研究在某种意义上就是可行性研究。 1 2 算法的性质 算法分析与算法复杂度 • 算法可以理解为动作序列的有限集合 • 算法分析的任务是对设计出的每一个具体的算 法，利用数学工具，讨论其复杂度，探讨具体 算法对问题的适应性 • 仅有一个初始动作 • 算法的复杂度分时间复杂度和空间复杂度。 • 每个动作的后继动作是确定的 • 计算机理论科学中，按照计算复杂性研究问题 • 算法的终止表示问题得到解答或问题没有解答 求解的难易性，可把问题分为P类、NP类和 NP-完全类。 3 4 算法的效率 算法的效率(cont) 对于一个问题通常有多种解法（算法），应 目标1涉及到软件工程原理 该选择哪一种呢？ 目标2涉及到数据结构与算法分析 计算机程序设计的核心有两个目标（有时它 们互相冲突） 本课程主要讲的是与目标2有关的问题 1. 设计一种容易理解、编码和调试的算法 2. 设计一种能有效利用计算机资源的算法 怎样度量算法的代价、效率呢？ 5 6 如何度量效率? 怎样比较两种算法解决问题的效 率呢？ 1. 实验比较（运行程序） 2. 渐近算法分析Asymptotic Algorithm Analysis • 实验比较 – 用源程序分别实现这两种算法，然后输入适 关键资源: 当的数据运行，测算两个程序各自的开销 影响运行时间的因素: –