算法设计与分析基础第2版清华出版社算法分析第1章.ppt

欢迎学习 算法设计与分析 算法设计与分析基础 主讲教师：杨群生 计算机学院 绪论 为什么学习算法?对于一个即将从事计算机专业的人士来说,无论从理论还是从实践的角度,学习算法都是有必要的.从实践的角度来看,我们必须了解计算机领域中不同问题的一系列标准算法:此外,我们还要具备设计算法和分析效率的能力.从理论的角度来看,对算法的研究(有时称为“算法学”)已经被公认为是计算机科学的基石。 本章学习内容 1.1节介绍算法的概念 1.2节讲述算法问题求解 1.3节讨论几种问题类型 1.4节对基本的数据结构做了一番回顾 1.1 算法的概念 什么是算法？ 算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。 问题 算法 “computer” 输入 输出 图1.1 算法的概念 作为阐明算法概念的几个例子,本节会讨论3种方法,用于解决同一个问题:计算两个整数的最大约数。这些例子会帮助我们阐明几个要点： 算法的每一个步骤都必须清晰，明确，来不得半点含糊。 算法所处理的输入的值域必须仔细定义。 同样一种算法可以用几种不同的形式来描述。 可能存在几种解决相同问题的算法。 针对同一个问题的算法可能会基于完全不同的解题思路，而且解题目速度也会有显著不同。 欧几里得算法基于的方法是重复应用下列等式，直到m mod n等于0； gcd(m ,n)=gcd(n ,m mod n) (m mod n 表于m除以n之后的余数) 用于计算gcd(m,n)的欧几里得算法 第一步：如果n=0,返回m的值作为结果，同样过程结束；否则进入第二步。 第二步：用n去除m，将余数赋给r。 第三步：将n的值赋给m，将r的值赋给n，返 回第一步。 用于计算gcd(m,n)连续整数检测算法 第一步：将min{m,n}的值赋给t。 第二步：m除以t，如余数为0。进入第三步；否则，进入第四步。 第三步：n除以t，如果余数为0，返回t的值作为结果；否则，进入第四步。 第四步：把t的值减1。返回第二步。 中学里计算gcd(m,n)过程 第一步：找到m的所有质因数。 第二步：找到n的所有质因数。 第三步：从第一步和第二步求得的质因数分解式中找出所有的公因数（如果p是一个公因数，而且在m和n的质因数分解式分别出现过pm 和pn次，那么应该将p重复min{pm, pn}次 ）。 第四步：将第三步中找到质因数相乘，其结果作为给定数字的最大公约数。 1.2 算法问题求解基础 1.2.1 理解问题 从实践的观点来看，在设计一个算法前我们需要做的第一件事就是完全理解所给出的问题。仔细阅读问题的描述，如有任何疑惑就把疑问提出来，手工处理一些小例子，考虑一下特殊情况，有必要的话再继续提出疑问。 理解问题 决定； 计算方法； 精确和近似的解法； 数据结构； 算法设计技术 设计算法 正确性证明 分析算法 根据算法写代码 算法的设计和分析过程 1.2.2 了解计算设备的性能 一旦完全了了待处理的问题，我们就需要了解将要运行的计算机设备的性能。 1.2.3 在精确解法和近似解法间做先择 接下来主要讨论如何在精确的解法和近似的解法间做选择。前一种我们称之为精确算法，后一种则称为近似算法。 1.2.4 确定适当的数据结构 有些算法并不要求输入数据具有精巧的表现形式，但有些算法的确需要基于一些精心设计的数据结构。 1.2.5 算法设计技术 算法设计技术（也称为“策略”或者“范例”）是用算法解题的一般性方法，用于解决不同计算领域的多种问题。 1.2.6 详细表述算法的方法 我们一旦设计了一个算法，就需要用一定的方式对其进行详细描述。伪代码是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确，而且伪代码生成的算法描述往往会更简洁。 1.2.7 证明算法的正确性 一旦完成了以算法的描述，我们必须证明它的正确性。也就是说，我们必须证明对于每一个合法输入，该算法都会在有限的时间内输出一个满足要求的结果。 1.2.8 分析算法 我们常常希望我们的算法具有许多良