算法分析1.ppt

算法设计与分析基础 任课教师：顾国生 E-mail：gsgu@ 电话广东工业大学计算机学院 绪论 为什么学习算法?对于一个即将从事计算机专业的人士来说,无论从理论还是从实践的角度,学习算法都是有必要的.从实践的角度来看,我们必须了解计算机领域中不同问题的一系列标准算法:此外,我们还要具备设计算法和分析效率的能力.从理论的角度来看,对算法的研究(有时称为“算法学”)已经被公认为是计算机科学的基石。 1.1 算法的概念 什么是算法？ 算法是一系列解决问题的清晰指令，也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。 用于计算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。返回第二步。 求连续素数序列的“埃拉托色尼筛”法: Sieve(n) For p=2 to n do //设立数组A[2]~A[n] A[p]=p For p=2 to do // if A[p]≠0, j=p*p while j=n do A[j]=0 // 表示将A中对应元素标记为消去 j=j+p i=0 // 将A中剩余的元素复制到数组L供连续输出 For p=2 to n do if A[p]≠0, L[i]=A[p] i=i+1 Return L 1.2 算法问题求解基础 1.2.2 了解计算设备的性能 一旦完全了了待处理的问题，我们就需要了解将要运行的计算机设备的性能。 1.2.3 在精确解法和近似解法间做先择 接下来主要讨论如何在精确的解法和近似的解法间做选择。前一种我们称之为精确算法，后一种则称为近似算法。 1.2.4 确定适当的数据结构 有些算法并不要求输入数据具有精巧的表现形式，但有些算法的确需要基于一些精心设计的数据结构。 1.2.5 算法设计技术 算法设计技术（也称为“策略”或者“范例”）是用算法解题的一般性方法，用于解决不同计算领域的多种问题。 1.2.6 详细表述算法的方法 我们一旦设计了一个算法，就需要用一定的方式对其进行详细描述。伪代码是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确，而且伪代码生成的算法描述往往会更简洁。 1.2.7 证明算法的正确性 一旦完成了以算法的描述，我们必须证明它的正确性。也就是说，我们必须证明对于每一个合法输入，该算法都会在有限的时间内输出一个满足要求的结果。 1.2.8 分析算法 我们常常希望我们的算法具有许多良好的特性。除正确性以外，最重要的特性就是“效率”了。实际上，算法有两种效率：时间效率和空间效率。时间效率显示了算法运行得有多快；而空间效率则显示了算法需要多额外的存储空间。 1.2.9 为算法写代码 绝大多数算法注定以计算机程序的形式实现。 1.3.1 排序 排序问题要求我们按照升序重新排列给定列表中的数据项。当然，为了让这个问题有意义，列表中数据项的特性应该允许这种排列。 排序算法有两个特性特别值得一提。如果一个排序算法保留了实值无素在输入中的相对顺序，它被称为是稳定的。第二个特性是算法需要的额外储空间。如果一个算法除了个别存储单元以外，不需要额外存储空间，我们把它称为是在位的。 1.3.2 查找 查找问题涉及到从给定的集合（或者是多重集，它允许几个无素具有相同的值）中找寻一个给定的值，称为查找键。对于查找来说，也没有一种算法对于任何情况都是最适合的。有些算法速度比其他算法快，但却需要较多的存储空间；有些算法速度非常快，但仅适用