算法第1章绪论与算法效率分析

《算法第1章绪论与算法效率分析》由会员分享，可在线阅读，更多相关《算法第1章绪论与算法效率分析（90页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析 授课教师：钟世芬 电话：87720985 课件制作：黄襄念老师 感谢黄老师的辛劳制作！,参考教材,参考教材,作者：（美）Anany Levitin 译者：潘彦 出版社：清华大学 丛书名：国外经典教材 计算机 科学与技术 定价： 45.00￥ 市场价：36.00￥,第1章 绪论与算法效率分析,算法的概念 算法问题求解过程 重要的问题类型 基本数据结构回顾 算法效率分析框架 渐进符号和基本效率类型 非递归算法效率分析 递归算法效率分析 本章习题 参考教材,算法的概念,算法的概念 为什么学习算法： David Harel 在算法：计算的灵魂中的描述： 算法不仅是计算机科学的一个分支，

2、更是计算机科学的核心。而且， 可以毫不夸张地说，它和绝大多数的科学、商业和技术是相关的。 对于一个即将从事计算机专业的人士来说，学习算法都是必要的， 了解计算领域中不同问题的一系列标准算法，并且具备设计新算法和 分析算法效率的能力。 随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和 研究算法。 算法应用领域例： （1）工作方面：AI（人工智能）、PR（模式识别）算法的研究。 （2）生活方面：机器博弈算法的研究（象棋、围棋等）。,算法设计与数据结构,算法设计与数据结构： 数据结构主要关心的是不同的数据结构（逻辑的）在计算机解题中的 作用和效率，而算法设计与分析关心的是不同的算法设计的

3、实用性和 效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。 算法 数据结构 程序 程序功能设计包括：行为设计和结构设计。 行为设计：对要解决的问题，提出达到目的所需要实施的步骤序列。 并对这些步骤加以必要细化，用某种方法进行描述，其 结果就是算法。 算法设计（得到具体问题的算法） 结构设计：设计算法所需要的高效的数据结构。 有了好的算法和数据结构，以某种程序设计语言予以实现程序。 算法的定义： 什么是算法？没有一个公认的用语来描述。针对其含义的基本共识： 算法是一系列解决问题的清晰的指令，对符合一定规范的输入，能在有限时间内获得所要求的输出。图示如下：,算法的几个特点,算法的几个特

4、点：（定义的内涵） （1）有穷性：有限时间内完成。如计算n！；穷举法解旅行商问题。 （2）确定性：算法的每一步必须是确定的，不能有两可的解释。 （3）可行性：一是每一步必须是有意义的，如约束优化的可行域判定； 二是每一步能够达到预期目的。如求sinx1的解不可行。 （4）输入：输入的值域必须仔细定义；（下例可见） （5）输出：获得问题的解，无输出的算法是没有意义的。（多种） （6）同一问题求解，可能存在几种不同的算法，执行效率有所差异。,算法一：欧氏几何求最大公约数,算法例：求两个不全为零的非负整数 m 和 n 的最大公约数 记号一：记 m 和 n 的最大公约数为 gcd(m, n)，表示能够

5、整除 m 和 n （即余数为零）的最大正整数。 记号二：m mod n 表示 m 除以 n 所得余数。 算法一：欧几里得（公元前3世纪）所著几何原本解法 重复执行下列等式，直到 m mod n（余数）等于0：（结束条件） gcd(m, n) = gcd(n, m mod n) 最后 m 的取值就是最大公约数。 例如 gcd(60, 24) 计算如下： gcd(m, n) = gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12（等式） 欧氏算法的结构化描述： 1. 如果 n = 0，返回 m 值为结果输出，计算结束！否则，转2步； 2. r = m mod n

6、;（赋值） 3. m = n, n = r（赋值）, 转1步。（变量交换）,欧氏算法的伪码描述,欧氏算法的伪码描述：（伪码较流程图描述更为先进，建议采用） 模块：Euclid(m, n) / 计算m,n最大公约数的欧氏算法 / 输入：两个不全为0的非负整数 m n / 输出：m，n 的最大公约数 while n0 do r m mod n mn n r return m 问题一：该算法一定收敛吗？（是否会停止循环，输出结果呢）,观察分析：设 m n，r = m mod n 每一次循环（m mod n）后，新 n 值会变小，但不会变成负数；即 除数 n 大于余数 r（n r 0）。余数作为下一轮

7、新 n 值（nr）， 因此 ，n 越来越小，最终变成 0。,问题二： 如果 m 和 n 没有公约数呢？本算法是否支持这种情况。,答案：支持。 例子： (63, 22)(22, 19) (19, 3) (3,1) (1,0) 1,算法二：连续检测算法,算法二：连续整数检测算法 连续检测算法的设计思想： 根据定义，最大公约数不会大于 m 和 n，设 t = min m, n 。我们现在 开始检测 t 是否为公约数：若是公约数，那么 t 就是最大公约数；否则， 我们就将 t 简单地减1（t = t - 1 或 t - = 1 或 t - -），继续判定 t 是否为 公约数：若是则输出结果；否则继续上

8、述循环，即 t 继续减下去，最终 减到 1 为止。例如 (64, 24)，先用 t = 24 尝试，然后是23，22， 当尝试到 12 时，算法结束。（整除的判定，即余数为0） 连续检测算法的结构化描述： 1. 将 min m, n 赋值给 t ； 2. m 除以 t ，若余数为0，转3步；否则，转 4 步； 3. n 除以 t ，若余数为0，则输出结果；否则，转 4 步； 4. t 值减 1，返回第 2 步。 注意，该算法忽略了一些编程时的细节问题：输入值的合法性判定。若 输入 m 或 n 为0 值时，算法出错。所以，输入值的值域检查很重要。,算法三：中学计算最大公约数的过程,算法三：中学计

9、算最大公约数质因数算法 算法设计思想： 1. 找出 m 所有质因数；（不可以再被整除的因数） 2. 找出 n 所有质因数；（包括重复质因数，如 8 = 222，三个2） 3. 从1、2 两步所得质因数中找出所有的公因数（包括重复的公因数）。 4. 将 3 步所得公因数相乘，得到结果（最大公约数）。 举例：求 gcd(60, 24) 先找到其质因数分解式：60 = 2235； 24 = 2223 可得最大公约数为：gcd(60, 24) = 223 = 12 根据上述思想设计算法，尚有两个问题未得到解决： 问题 1：设计求 m 和 n 所有质因数算法；（用各自的质因数数组存放） 问题 2：设计求

10、两数组公共元素的算法；（有序数组） 问题 2 的算法较容易设计，请大家自行设计。 下面考虑问题 1 的算法设计：求正整数 N 的全部质因数算法。,求正整数 N 的全部质因数的算法,求正整数 N 全部质因数的算法 算法设计： 给定正整数N的全部质因数都不会大于N，于是我们可以想办法首先产生 一个小于N的质数序列（有序质数数组存放），然后用这些质数去除N， 若能整除（余数为0），那么该质数就是质因数；否则，就不是质因数。 当质数数组中所有元素都去除过N以后，即得到N的全部质因数。现在， 问题发生了转化，即：设计一个小于给定正整数N的质数序列产生算法， 我们姑且称之为质数发生器。 质数发生器算法设计

11、： 埃拉托色尼（利比亚，公元前200年）筛 算法思想：消去法。 1. 产生一个2N的连续整数有序序列（小到大）作为候选质数，k = 1； 2. kk + 1，消去（丢弃）序列中为 k 的倍数的数（整除余数判定）； 3. 避免重复消去：如4，在消去 2 的倍数时已被消去，消去3的倍数后， 直接消去5的倍数，跳过 k = 4 这轮的消去；6，8 等也如此。理由？ 4的倍数肯定是2的倍数，6、8的倍数也肯定是2的倍数。,质数发生器算法举例,质数发生器算法举例： N = 25，要求得到小于N的所有质数序列 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

12、 21 22 23 24 25 2 3 5 7 9 11 13 15 17 19 21 23 25 2 3 5 7 11 13 17 19 23 25 2 3 5 7 11 13 17 19 23 2 3 5 7 11 13 17 19 23 进行到消去7的倍数时，已没有要消去的数，消去停止，输出结果。 编程实现上述算法时，数据结构需要仔细考虑。这里数据结构问题就是 设计多少个一维数组来存放算法的输入数据、中间数据、输出数据。 比如，可设计一种简单方案： 1. 用一维数组 InN-1 存放2N的整数（小到大序）；In0 = 2 2. 从 Ini = k 开始的每一轮(i)消去时，将数组中该轮k

13、的倍数数置0。 后续消去时，若 Ini = k = 0，则跳过消去该k的倍数，避免重复。,算法问题求解过程,算法问题求解过程,理解问题,了解设备性能 决定计算方法： 精确的或近似的解法 确定数据结构 考虑算法设计技术,设计算法,正确性证明,分析算法,根据算法写代码,算法设计与分析过程,算法：算法是问题的程序化解决方案。 解决方案本身不是问题的答案，而是获得答案的精确指令。正是因为强调这个精确的结构化过程，使得计算机科学与其他学科特别是理论数学区别开来。,理解问题,理解问题 这是实践中设计一个算法前必须做的第一件事情，即完全理解清楚该 问题，若有任何疑惑就把疑问提出来，手工处理一些小例子，考虑下

14、 特殊情况，这是一个不断提问的过程，直到彻底搞透彻问题各方面。 典型问题： 有几大类问题会频繁出现于计算机应用中，稍后阐述。如果待解决的 问题属于其中一类，我们就可以用一个已知的算法求解。同时，还须 了解清楚该算法的执行过程和优缺点，这对我们解决问题很有帮助， 特别是有几个算法可供选择时。 输入问题： 算法的一个输入，确定了该算法所解问题的一个实例。严格确定算法 处理的实例范围（边界检查）非常重要。如果这一步有所疏忽的话， 将可能导致算法对大多数输入能正确处理，但在遇到某些“边界值”时 就出错，甚至使系统彻底崩溃掉。因此，一个正确的算法，能够处理 “所有的”、“合法的” 输入。（算法没有限制的

15、输入即为合法输入）,了解设备性能,了解设备性能 串行算法（顺序算法） 今天使用的大多数算法依然注定要靠运行于冯诺伊曼机器上的代码来 实现。这种计算机体系结构的重点在于随机存取机（Random-Access Machine, RAM）。它最主要思想是：指令逐条执行，每次执行一步 操作。相应地，设计运行于这种机器上的算法即串行（顺序）算法。 并行算法 设计运行于并行计算机上的算法即并行算法。并行计算机可以在同一 时间执行多条指令，即并行计算。这里面包含两层意思：一是计算机 体系结构上的并行（硬件），一是算法本身的并行运算（软件）。在 可以预见的将来，学习RAM模型下算法设计与分析的经典技术仍然是 算法学的基石。 计算速度和存储容量： 绝大多数计算机学家倾向于以一种独立于特定机型的方式研究算法， 这是科学研究。若是实用工具，设计的算法取决于具体问题。如海量 数据、实时性要求等，这时需要意识到计算速度和存储容量问题。,精确算法和近似算法,精确算法和近似算法 选择近似算法的两方面原因： 1. 无法求精确解。例如：（参阅计算方法有关书籍） 1）多种解非线性方程（超越方程或高次方程）的近似算法。 如折半查找法，0.618法（黄金分割法），牛顿切线法等等。 2）数值积分法。诸如： 找不到原函数的定积分，无法精确积分；被积函数是表格函数 即离散数据点的定积分。算法如