算法第一章绪论与算法效率分析.ppt

算法设计与分析 授课教师：钟世芬 电话 课件制作：黄襄念老师 感谢黄老师的辛劳制作！ 参考教材 参考教材 第1章 绪论与算法效率分析 算法的概念 算法问题求解过程 重要的问题类型 基本数据结构回顾 算法效率分析框架 渐进符号和基本效率类型 非递归算法效率分析 递归算法效率分析 本章习题 参考教材 算法的概念 算法的概念 为什么学习算法： David Harel 在《算法：计算的灵魂》中的描述： 算法不仅是计算机科学的一个分支，更是计算机科学的核心。而且， 可以毫不夸张地说，它和绝大多数的科学、商业和技术是相关的。 对于一个即将从事计算机专业的人士来说，学习算法都是必要的， 了解计算领域中不同问题的一系列标准算法，并且具备设计新算法和 分析算法效率的能力。 随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和 研究算法。 算法应用领域例： （1）工作方面：AI（人工智能）、PR（模式识别）算法的研究。 （2）生活方面：机器博弈算法的研究（象棋、围棋等）。 算法设计与数据结构 算法设计与数据结构： 数据结构主要关心的是不同的数据结构（逻辑的）在计算机解题中的 作用和效率，而算法设计与分析关心的是不同的算法设计的实用性和 效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。 算法 ＋ 数据结构 ＝ 程序 程序功能设计包括：行为设计和结构设计。 行为设计：对要解决的问题，提出达到目的所需要实施的步骤序列。 并对这些步骤加以必要细化，用某种方法进行描述，其 结果就是算法。—— 算法设计（得到具体问题的算法） 结构设计：设计算法所需要的高效的数据结构。 有了好的算法和数据结构，以某种程序设计语言予以实现——程序。 算法的定义： 什么是算法？没有一个公认的用语来描述。针对其含义的基本共识： 算法是一系列解决问题的清晰的指令，对符合一定规范的输入，能在有限时间内获得所要求的输出。图示如下： 算法的几个特点 算法的几个特点：（定义的内涵） （1）有穷性：有限时间内完成。如计算n！；穷举法解旅行商问题。 （2）确定性：算法的每一步必须是确定的，不能有两可的解释。 （3）可行性：一是每一步必须是有意义的，如约束优化的可行域判定； 二是每一步能够达到预期目的。如求sinx1的解不可行。 （4）输入：输入的值域必须仔细定义；（下例可见） （5）输出：获得问题的解，无输出的算法是没有意义的。（多种） （6）同一问题求解，可能存在几种不同的算法，执行效率有所差异。 算法一：欧氏几何求最大公约数 算法例：求两个不全为零的非负整数 m 和 n 的最大公约数 记号一：记 m 和 n 的最大公约数为 gcd(m, n)，表示能够整除 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;（赋值） 3. m = n, n = r（赋值）, 转1步。（变量交换） 欧氏算法的伪码描述 欧氏算法的伪码描述：（伪码较流程图描述更为先进，建议采用） 模块：Euclid(m, n) // 计算m,n最大公约数的欧氏算法 // 输入：两个不全为0的非负整数 m n // 输出：m，n 的最大公约数 while n≠0 do { r ← m mod n m←n n ←r } return m 问题一：该算法一定收敛吗？（是否会停止循环，输出结果呢） 算法二：连续检测算法 算法二：连续整数检测算法 连续检测算法的设计思想： 根据定义，最大公约数不会大于 m 和 n，设 t = min { m, n