《算法 第1章 绪论与算法效率分析》由会员分享，可在线阅读，更多相关《算法 第1章 绪论与算法效率分析（90页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析授课教师：钟世芬 电话：87720985课件制作：黄襄念老师感谢黄老师的辛劳制作！西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念参考教材 参考教材作者：（美）Anany Levitin 译者：潘彦出版社：清华大学丛书名：国外经典教材 计算机科学与技术定价： 45.00￥市场价：36.00￥西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念 编编 eMail eMail ： Tel:Tel:（028028）89585218, 8772203789585218, 87722037第1章 绪论与算法效率分析 算法的概念 算法问题求解过程 重要的问题类型 基本
2、数据结构回顾 算法效率分析框架 渐进符号和基本效率类型 非递归算法效率分析 递归算法效率分析 本章习题 参考教材西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法的概念 算法的概念w 为什么学习算法：David Harel 在算法：计算的灵魂中的描述：算法不仅是计算机科学的一个分支，更是计算机科学的核心。而且，算法不仅是计算机科学的一个分支，更是计算机科学的核心。而且，可以毫不夸张地说，它和绝大多数的科学、商业和技术是相关的。可以毫不夸张地说，它和绝大多数的科学、商业和技术是相关的。对于一个即将从事计算机专业的人士来说，学习算法都是必要的，了解计算领域中不同问题的一系列标准算法
3、，并且具备设计新算法和分析算法效率的能力。随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和研究算法。w 算法应用领域例：（1）工作方面：AI（人工智能）、PR（模式识别）算法的研究。（2）生活方面：机器博弈算法的研究（象棋、围棋等）。西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法设计与数据结构w 算法设计与数据结构：数据结构主要关心的是不同的数据结构（逻辑的）在计算机解题中的作用和效率，而算法设计与分析关心的是不同的算法设计的实用性和效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。算法 数据结构 程序程序功能设计包括：行为设计和结构设计。行为设计：对
4、要解决的问题，提出达到目的所需要实施的步骤序列。并对这些步骤加以必要细化，用某种方法进行描述，其结果就是算法。 算法设计（得到具体问题的算法）结构设计：设计算法所需要的高效的数据结构。有了好的算法和数据结构，以某种程序设计语言予以实现程序。w 算法的定义：什么是算法？没有一个公认的用语来描述。针对其含义的基本共识：算法算法是一系列解决问题的清晰的是一系列解决问题的清晰的指令指令，对符合一定规范的，对符合一定规范的输入输入，能在，能在有有 限时间限时间内获得所要求的内获得所要求的输出输出。图示如下：西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法的几个特点w 算法的几个特点：（
5、定义的内涵）（1）有穷性：有限时间内完成。如计算n！；穷举法解旅行商问题。（2）确定性：算法的每一步必须是确定的，不能有两可的解释。（3）可行性：一是每一步必须是有意义的，如约束优化的可行域判定；二是每一步能够达到预期目的。如求sinx1的解不可行。（4）输入：输入的值域必须仔细定义；（下例可见）（5）输出：获得问题的解，无输出的算法是没有意义的。（多种）（6）同一问题求解，可能存在几种不同的算法，执行效率有所差异。COMPUTER问 题算 法输 入输 出西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法一：欧氏几何求最大公约数v 算法例：求两个不全为零的非负整数 m 和 n
6、的最大公约数记号一：记 m 和 n 的最大公约数为 gcd(m, n)，表示能够整除 m 和 n（即余数为零）的最大正整数。记号二：m mod n 表示 m 除以 n 所得余数。w 算法一：欧几里得（公元前3世纪）所著几何原本解法重复执行下列等式，直到 m mod n（余数）等于0：（结束条件）gcd(mm, n) = gcd(n n, m mod n)最后 m 的取值就是最大公约数。例如 gcd(60, 24)gcd(60, 24) 计算如下：gcd(mm, n) = gcd(6060, 24) = gcd(24(24, 12) = gcd(1212, 0) = 1212（等式）欧氏算法的结
7、构化描述：1. 如果 n = 0，返回 m 值为结果输出，计算结束计算结束！否则，转2步；2. r = m mod n;（赋值）3. m = n, n = r（赋值）, 转1步。（变量交换）西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念欧氏算法的伪码描述欧氏算法的伪码描述：（伪码较流程图描述更为先进，建议采用） 模块：Euclid(m, n)/ 计算m,n最大公约数的欧氏算法/ 输入：两个不全为0的非负整数 m n/ 输出：m，n 的最大公约数while n0 do r m mod nmnn r return mm问题一：该算法一定收敛吗？问题一：该算法一定收敛吗？（是否会停止
8、循环，输出结果呢） 观察分析观察分析：设 m n，r = m mod n 每一次循环（m mod n）后，新 n 值会变小，但不会变成负数；即 除数 n 大于余数 r（n r 0）。余数作为下一轮新 n 值（nr）， 因此 ，n 越来越小，最终变成 0。问题二：问题二： 如果如果 m m 和和 n n 没有公约数呢？没有公约数呢？本算法是否支持这种情况。本算法是否支持这种情况。答案：支持。例子： (63, 22)(22, 19) (19, 3)(3,1) (1,0) 1 1西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法二：连续检测算法w 算法二：连续整数检测算法连续检测算法
9、的设计思想：根据定义，最大公约数不会大于最大公约数不会大于 m m 和和 n n，设 t = min m, n 。我们现在开始检测 t 是否为公约数：若是公约数，那么 t 就是最大公约数；否则，我们就将 t 简单地减1（t = t - 1 或 t - = 1 或 t - -），继续判定 t 是否为公约数：若是则输出结果；否则继续上述循环，即 t 继续减下去，最终减到 1 为止。例如 (64, 24)，先用 t = 24 尝试，然后是23，22，当尝试到 12 时，算法结束。（整除的判定，即余数为0）连续检测算法的结构化描述：1. 将 min m, n 赋值给 t ；2. m 除以 t ，若余数
10、为0，转3步；否则，转 4 步；3. n 除以 t ，若余数为0，则输出结果；否则，转 4 步；4. t 值减 1，返回第 2 步。注意，该算法忽略了一些编程时的细节问题：输入值的合法性判定。若输入 m 或 n 为0 值时，算法出错。所以，输入值的值域检查很重要。西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法三：中学计算最大公约数的过程w 算法三：中学计算最大公约数质因数算法算法设计思想：1. 找出 m 所有质因数；（不可以再被整除的因数）2. 找出 n 所有质因数；（包括重复质因数，如 8 = 222，三个2）3. 从1、2 两步所得质因数中找出所有的公因数（包括重复的公
11、因数）。4. 将 3 步所得公因数相乘，得到结果（最大公约数）。举例：求 gcd(60, 24)先找到其质因数分解式：60 = 2 22 23 35； 24 = 22 22 23 3可得最大公约数为：gcd(60, 24) = 223 = 12根据上述思想设计算法，尚有两个问题未得到解决：问题 1：设计求 m 和 n 所有质因数算法；（用各自的质因数数组存放）问题 2：设计求两数组公共元素的算法；（有序数组）问题 2 的算法较容易设计，请大家自行设计。下面考虑问题 1 的算法设计：求正整数 N 的全部质因数算法。西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念求正整数 N 的全部
12、质因数的算法求正整数 N 全部质因数的算法算法设计： 给定正整数N的全部质因数都不会大于N，于是我们可以想办法首先产生一个小于N的质数序列（有序质数数组存放），然后用这些质数去除N，若能整除（余数为0），那么该质数就是质因数；否则，就不是质因数。当质数数组中所有元素都去除过N以后，即得到N的全部质因数。现在，问题发生了转化，即：设计一个小于给定正整数设计一个小于给定正整数N N的质数序列产生算法的质数序列产生算法，我们姑且称之为质数发生器。 质数发生器算法设计： 埃拉托色尼（利比亚，公元前200年）筛算法思想：消去法。 1. 产生一个2N的连续整数有序序列（小到大）作为候选质数，k = 1；2
13、. 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 21 22 23 24 252 2 3 5 7 9 11 13 15 17 19 21 2
14、3 252 3 3 5 7 11 13 17 19 23 252 3 5 7 11 13 17 19 23 2 3 5 7 7 11 13 17 19 23进行到消去7的倍数时，已没有要消去的数，消去停止，输出结果。编程实现上述算法时，数据结构需要仔细考虑。这里数据结构问题就是设计多少个一维数组来存放算法的输入数据、中间数据、输出数据。比如，可设计一种简单方案：1. 用一维数组 InN-1 存放2N的整数（小到大序）；In0 = 22. 从 Ini = k 开始的每一轮(i)消去时，将数组中该轮k的倍数数置0。后续消去时，若 Ini = k = 0，则跳过消去该k的倍数，避免重复。西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念算法问题求解过程 算法问题求解过程理解问题了解设备性能 决定计算方法： 精确的或近似的解法 确定数据结构 考虑算法设计技术设计算法正确性证明分析算法根据算法写代码算法：算法是问题的程序化解决方案算法是问题的程序化解决方案。解决方案本身不是问题的答案，而是获得答案 的精确指令。正是因为强调这个精确的结构化 过程，使得计算机科学与其他学科特别是理论 数学区别开来。西华大学数学与计算机学院西华大学数学与计算机学院 黄襄念黄襄念理解问题v 理解问题这是实践中设计
