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

算法设计与分析 授课教师：钟世芬 电话：87720985 课件制作：黄襄念老师 感谢黄老师的辛劳制作！,参考教材,参考教材,作者：（美）Anany Levitin 译者：潘彦 出版社：清华大学 丛书名：国外经典教材 计算机 科学与技术 定价： 45.00￥ 市场价：36.00￥,第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 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）。余数作为下一轮新 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 是否为 公约数：若是则输出结果；否则继续上述循环，即 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 值时，算法出错。所以，输入值的值域检查很重要。,算法三：中学计算最大公约数的过程,算法三：中学计算最大公约数质因数算法 算法设计思想： 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：设计求两数组公共元素的算法；（有序数组） 问题 2 的算法较容易设计，请大家自行设计。 下面考虑问题 1 的算法设计：求正整数 N 的全部质因数算法。,求正整数 N 的全部质因数的算法,求正整数 N 全部质因数的算法 算法设计： 给定正整数N的全部质因数都不会大于N，于是我们可以想办法首先产生 一个小于N的质数序列（有序质数数组存放），然后用这些质数去除N， 若能整除（余数为0），那么该质数就是质因数；否则，就不是质因数。 当质数数组中所有元素都去除过N以后，即得到N的全部质因数。现在， 问题发生了转化，即：设计一个小于给定正整数N的质数序列产生算法， 我们姑且称之为质数发生器。 质数发生器算法设计： 埃拉托色尼（利比亚，公元前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 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的倍数数置0。 后续消去时，若 Ini = k = 0，则跳过消去该k的倍数，避免重复。,算法问题求解过程,算法问题求解过程,理解问题,了解设备性能 决定计算方法： 精确的或近似的解法 确定数据结构 考虑算法设计技术,设计算法,正确性证明,分析算法,根据算法写代码,算法设计与分析过程,算法：算法是问题的程序化解决方案。 解决方案本身不是问题的答案，而是获得答案的精确指令。正是因为强调这个精确的结构化过程，使得计算机科学与其他学科特别是理论数学区别开来。,理解问题,理解问题 这是实践中设计一个算法前必须做的第一件事情，即完全理解清楚该 问题，若有任何疑惑就把疑问提出来，手工处理一些小例子，考虑下 特殊情况，这是一个不断提问的过程，直到彻底搞透彻问题各方面。 典型问题： 有几大类问题会频繁出现于计算机应用中，稍后阐述。如果待解决的 问题属于其中一类，我们就可以用一个已知的算法求解。同时，还须 了解清楚该算法的执行过程和优缺点，这对我们解决问题很有帮助， 特别是有几个算法可供选择时。 输入问题： 算法的一个输入，确定了该算法所解问题的一个实例。严格确定算法 处理的实例范围（边界检查）非常重要。如果这一步有所疏忽的话， 将可能导致算法对大多数输入能正确处理，但在遇到某些“边界值”时 就出错，甚至使系统彻底崩溃掉。因此，一个正确的算法，能够处理 “所有的”、“合法的” 输入。（算法没有限制的输入即为合法输入）,了解设备性能,了解设备性能 串行算法（顺序算法） 今天使用的大多数算法依然注定要靠运行于冯诺伊曼机器上的代码来 实现。这种计算机体系结构的重点在于随机存取机（Random-Access Machine, RAM）。它最主要思想是：指令逐条执行，每次执行一步 操作。相应地，设计运行于这种机器上的算法即串行（顺序）算法。 并行算法 设计运行于并行计算机上的算法即并行算法。并行计算机可以在同一 时间执行多条指令，即并行计算。这里面包含两层意思：一是计算机 体系结构上的并行（硬件），一是算法本身的并行运算（软件）。在 可以预见的将来，学习RAM模型下算法设计与分析的经典技术仍然是 算法学的基石。 计算速度和存储容量： 绝大多数计算机学家倾向于以一种独立于特定机型的方式研究算法， 这是科学研究。若是实用工具，设计的算法取决于具体问题。如海量 数据、实时性要求等，这时需要意识到计算速度和存储容量问题。,精确算法和近似算法,精确算法和近似算法 选择近似算法的两方面原因： 1. 无法求精确解。例如：（参阅计算方法有关书籍） 1）多种解非线性方程（超越方程或高次方程）的近似算法。 如折半查找法，0.618法（黄金分割法），牛顿切线法等等。 2）数值积分法。诸如： 找不到原函数的定积分，无法精确积分；被积函数是表格函数 即离散数据点的定积分。算法如矩形法，梯形法，辛普森积分， 高斯积分等。 3）数值微分法。用差分近似微分，如5点差分法等。 4）插值与拟合。插值曲线未知或理论公式未知（得经验公式） 2. 问题复杂性： 由于某些问题固有的复杂性，用精确算法求解的时间耗费是不能够 接受的，如旅行商问题的精确求解：穷举法找 n 个城市之间的最短 巡回路径问题。,确定恰当的数据结构,确定合适的数据结构 有些算法对数据结构要求不高，但有些算法与数据的构造和重构有着 紧密的联系。面对一个实际问题，决定采用何种数据结构描述问题， 决定了设计不同的算法，对算法设计难度和执行效率有着重要影响。 比如，串结构存储，树结构存储，图结构存储对后续算法研制的难度 和时空复杂性起着决定性作用。如串的查找，树的查找，图的查找； 串的匹配，树的匹配，图的匹配。有一些算法就是针对某种数据类型 设计的。例如，解超大型线性方程组问题。由于受计算机内存RAM 容量限制，不能在内存中定义一个完整的系数矩阵，数据部分存放于 外存（硬盘）上，不断的调入、检索、覆盖、计算、写入等。 算法设计技术 算法设计技术 是用算法解题的一般性方法，用于解决不同领域的 多种问题。（有时也称“策略”或“范例”） 授人以鱼，不如授人以渔（Learning such techniques is akin to learning fish as opposed to being given a fish caught by somebody esle）,详细描述算法的方法,算法的详细描述方法 自然语言 自然语言固有的不严密性，要简单清晰地描述算法变得非常困难。 结构化文字（较流行的描述法之一） 如前述的欧氏算法描述。 流程图 早期占有统治地位，现已过时，只能在早期教材中找到踪迹。主要是 因为其在描述算法时非常不方便。 伪代码（较流行的描述法之一）（推荐采用） 伪码是自然语言和类编程语言的一种混合物，它比自然语言更精确， 生成的算法描述更为简洁。现今，计算机科学家们并没有对伪码形式 达成某一种共识，而是作者一种“方言”。幸运的是，这些方言在彼此 之间非常相似，使得任何熟悉一门现代编程语言的人都能完全理解。 当代计算机还不能将伪码直接“输入”计算机，需要把伪码算法用特定 编程语言写成程序算法的实现。（翻译过程：伪码算法）,证明算法的正确性,证明算法的正确性 算法的正确性 对于一个“合法输入”，该算法都能在有限时间内输出要求的结果。 比如：计算最大公约数的欧氏算法的正确性基于如下等式的正确性： gcd(m, n) = gcd(n, m mod n) 现在轮到证明这个等式的正确性了。该算法的每一次循环，n 值将会 变小的观察结果，以及算法会在 n 变为 0 时停止的事实。 算法正确性证明方法 某些算法的正确性证明非常简单，但某些算法证明却可能十分复杂。 一般采用数学归纳法，因为算法的迭代过程原本就提供了这种证明所 需要的一系列步骤。值得一提的是，用特定输入来追踪算法的执行是 很有意义的，但它并不能证明算法的正确性；反之，可通过列举反例 方法发现算法的不正确，再次设计或改进算法。 近似算法 常常证明该算法的误差不超出我们预定的范围。（收敛性） 事前误差估计法、事后误差检验法（收敛算法的迭代停止条件）。,算法设计的几个问题,算法设计的几个问题 算法的效率： 空间效率和时间效率，即时空效率。（后面讲解算法效率分析） 时空效率即运行算法所需要耗费的空间（RAM）和时间。随着计算机 硬件系统的飞速发展，空间效率不象早期要求的那样高，而着重考虑 时间效率。一般来说，宁愿以空间换时间。 算法的简单性： 简单就象“美丽”一样，很大程度上取决于审视者的眼光。（主观性） 简单性仍然是需要努力实现的一个算法特性。因为，简单的算法更易 理解和实现（软件工程），相应的程序也往往包含较少的BUG。 算法的一般性：包含解决问题的一般性、接受输入的一般性 解决问题的一般性：比如判断两个整数是否互质。可以设计一个一般 算法：计算两个整数的最大公约数，然后检验其是否等于1。 接受输入的一般性：即输入的范围。考虑：在当前问题所可能涉及的 范围内即可，不必过于追求扩大输入范围。比如实数域求解的问题， 没必要扩大到复数域，除非当前问题要求那样做。,重要的问题类型,重要的问题类型 在算法领域中，有一些问题吸引研究人员的特殊关注。大体来讲，要么 是问题具有实用上的重要性，要么是问题具有一些重要的特征： 排序问题 查找问题 串处理问题 图问题 组合问题 几何问题 数值问题 后续课程将用这些问题来说明不同的算法设计技术和算法的分析方法。,排序问题,排序问题 问题：按照升序（或降序）重新排列给定数表中的数据项。 应用例： 1）学校维护的学生信息记录； 2）图书馆维护的图书信息记录； 3）公司维护的员工信息记录； 键： 对记录排序时，我们需要选取一段特定信息（数据库中叫字段）作为 排序依据，这段特定信息称为键。 为什么需要排序列表 答案：便于查找。这就是为什么字典、电话簿、班级名册是排序的。 在实际的诸多算法中，排序是一个辅助步骤。 排序算法简介： 目前，已研制了几十种不同的排序算法，还在不断开发中。虽然有些 算法比其他算法更好，但没有一种算法在任何情况下都是最好的解决 方案。有些算法简单，但速度慢；有些算法适合排列驻留在内存中的,排序算法简介（续）,列表；而有些算法可以用来排列存储于磁盘上的大型文件；有些算法 适合于随机输入；而有些算法更适合于基本有序的列表。 排序算法的两个特性： 1）稳定的： 如果一个排序算法保留了等值元素在排序前后列表中的相对顺序， 称为稳定的。换句话说，输入列表中包含两个等值元素，它们的 位置分别为 i 和 j ，i j ；在排好序的输出列表中，它们的位置为 i 和 j，那么 i j （在前元素仍在前）。这种特性是有用的，如： 我们有一个按学生姓名字母排序的列表，现在要求按其平均成绩 排序输出。一个稳定排序算法输出的列表将会把同样成绩的学生 仍按其姓名字母序排列。 2）在位的： 如果一个排序算法除了个别存储单元外，不需要额外的存储空间， 则称为在位的。,查找和串处理,查找问题 查找：从给定集合（或多重集，有几个元素具有相同的值）中找到 一个给定的值，称为查找键。 多种查找算法： 顺序查找（挨个比较，时间效率较低），折半查找（时间效率极高， 但要求输入为排序列表）。还有些将原来的集合表示为另一种形式 以方便查找，如查找多重索引表。这对大型数据库存取来说，具有 重要意义。 考虑问题：要求开发一个特大型数据记录集的快速查找算法。 已知条件：数千万条记录存放于硬盘上，并可以添加、修改记录。 解决方案：选择怎样的数据结构和算法。 串处理 串：有字母和数字构成的序列（文本串）。由0和1构成的是位串。 串匹配：在给定文本中查找一个给定的“词”。 模式识别中的特征串描述、精确匹配与相似匹配问题。,图问题,图问题 图算法是最古老也最令人感兴趣的问题。 不严格定义的话，图是由一些顶点和边相连接（下节严格定义）。 图，可以对广泛的、各种各样的实际应用建模，如交通网络，通讯 网络，计算机网络，汉字笔画描述等等。 图的基本算法： 1. 图的遍历算法：如何一次访问图中所有的节点； 2. 最短路线算法：两个城市之间的最短路线是哪一条； 3. 有向图的拓扑排序：一系列过程的前提条件是一致的还是矛盾的。 某些图问题的困难： 旅行商问题：找出访问 n 个城市的最短路线，每个城市只访问一次。 图填色问题：用最少种的颜色为图中各顶点填色，并保证任何两个 邻接顶点的颜色不同。 图相似问题：如何判定两个不同的图是相似的。比如模式识别中用 图描述模式时，识别同一模式的变形模式会产生此问题。,组合问题和几何问题,组合问题 在给定集合中寻找一个组合对象，如一个排列、一个组合或一个子集 满足给定的要求，如成本最小化或价值最大化等。从更抽象的角度看 图填色问题和旅行商问题都是组合问题。 一般而言，组合问题是计算上最困难的问题，理由： 1. 随着问题规模的增大，组合对象的数量增长极快，产生组合爆炸； 2. 没有一种已知算法在可接受时间内，精确地解决绝大多数此类问题。 且大多数计算机科学家认为这样的算法并不存在。某些组合问题能 用效率较高的算法解决，但我们应把它归于运气和例外。如旅行商 问题的某些算法有时能得到最优结果。 几何问题 两个最经典的计算几何问题。 最近对问题：给定平面上 n 个点，求距离最近的两个点。 凸包问题：求给定点集中所有点包含在内的最小凸多边形。,数值问题,数值问题 这是另一个广泛的应用领域，涉及具有连续性的数学对象问题，如： 解方程和方程组（如代数、微分、偏微分、积分），计算定积分，求 函数值等等。对于大多数此类问题，我们只能近似求解。此外，这类 问题一般都要操作实数，实数在计算机内部只能近似表示，对近似数 大量算术操作导致误差积累，严重时使算法失效。所以，在数值算法 的设计和实现时，要注意误差分析和避免误差放大的设计技术。比如 两操作数求和时产生的“大数吃小数”现象。 问：大数吃小数现象是如何产生的？,基本数据结构回顾：数组,基本数据结构回顾 算法是对数据的操作，组织数据的特殊方式在算法设计和分析中扮演 重要角色，可将数据结构定义为相关数据项的组织方式。因此，数据 结构在算法设计中起重要作用。 线形数据结构 （1）数组：n 个相同数据类型的元素构成的序列，连续存储在内存中。 通过指定数组下标就能访问数组的元素。无论位于数组中 任何位置，其访问时间都相等，该特性将数组与链表截然 分开。数组可实现多种其他数据结构，较为突出的是串。 串来自于字母表中的字符序列，以一个特殊字符来标识串 结束。由 0 和 1 组成的串称为二进制串或者比特串。串的 常见操作包括计算串的长度，按字典序比较两个串的优先 顺序，连接两个串等。,基本数据结构回顾：链表,（2）链表：由一个或多个称为节点的元素构成的序列。每个节点包含 两类信息（域）：数据域和指针域。指针可以是多个，指向表中 其他元素（用NULL指针表示该节点没有后继节点）。单链表中 除了最后节点外，每个节点都包含一个指向下个元素的指针。 为了访问链表中某个特定元素， 需要从链表的第一个元素开始， 直到访问到该元素为止。因此，访问单链表中元素所需要的时间 与数组不同，依赖于该元素在链表中的位置。链表的优点是，其 节点在内存中不是连续分配的，需要一个才创建一个，不需事先 固定分配而占用多余的内存，对事先不能预知数据项多少的应用 特别适合。其常见操作为节点的插入和删除，通过重新连接链表 指针来实现。另外，尚有扩展结构如双链表、循环链表等。,null 数据项0,数据项1,数据项n-1 null,基本数据结构回顾：栈，队列，图,（3）栈：数据项的插入与删除均在尾端（栈顶）进行操作的列表。 在栈中添加一个元素称为进栈（PUSH），删除栈顶的一个元素 称出栈（POP）。该结构按照后进先出（LIFO, last-in-first-out） 方式运转。栈，具有众多优点，尤其是对于实现递归算法。 （4）队列：数据项的插入在列表的一端（队尾）进行，删除在另一端 （队头）进行，分别称为入队(enqueue) 、出队(dequeue) 。因此， 队列是按先进先出（FIFO, first-in-first-out）方式运行。 图 按照非正式定义，图可以认为是由平面上的节点（或称顶点）构成的 集合，某些顶点由边（或称为弧）的线段连接。按照图的正式定义： 图 G = ( V, E ) 是一个二元组，由两个集合来定义：一个有限集合V， 它的元素称为顶点；另一个有限集合E，其元素是一对顶点，称为边。,基本数据结构回顾：图,（1）无向图与有向图： 每对顶点之间没有顺序，顶点对 (u, v) 和 (v, u) 是相同的，即边是 没有方向的，称为无向图。否则，我们说边 (u, v) 的方向是从顶点 u 到顶点 v ， 称为有向图。 （3）完全图： 任意两个顶点之间都有边相连的图。 （4）稠密图： 相对完全图而言，所缺边数较少的图。 （5）稀疏图： 相对完全图而言，所缺边数较多的图。,有向图,基本数据结构回顾：图的表示,1. 图的两种表示法 邻接矩阵法： 用一个 n n 的布尔矩阵表示具有 n 个顶点的图，图中每个顶点用一行 和一列表示。若从第 i 个顶点到第 j 个顶点有边连接，则矩阵中第 i 行 第 j 列元素的值为1；若没有边连接，则该元素值为0。,邻接链表法： 每一个顶点用一个邻接链表表示。该链表 包括了与这个顶点邻接的所有顶点。,基本数据结构回顾：加权图,2. 加权图（带权图） 概念：加权图是一种给边赋值的图，这些值称为边的权重。 应用：比如求交通网或通讯网的最短路径问题。将每个城市定义为 一个顶点，用边连接两个城市，边的权重表示两个城市的距离。 表示：邻接矩阵或邻接链表都可以表示加权图。,加权无向图,邻接矩阵,邻接链表,基本数据结构回顾：路径和环,2. 路径和环 图的诸多特性中，有两个常用特性：连通性和无环性。均基于路径。 路径： 从起始顶点出发到终止顶点结束的一个顶点序列。 简单路径：一条路径不重复通过该路径上的任一顶点。（仅通过一次） 路径长度：路径顶点序列中所包含的顶点数减一。（等于边数） 连通图： 每一对顶点都存在一条路径连接的图。否则，称非连通图。,左图为非连通图，包括 两个连通的子图，也即 连通分量为2。,基本数据结构回顾：树,回路： 起点和终点都是同一个顶点，且长度大于 0 的简单路径。 无环图：不包括回路的图。（包括闭合路径的图或子图，如下） 树 概念：连通无回路的图。准确术语：自由树。 森林：若干树的集合。树与树之间不连通。 特点：边数比顶点数少一，即：顶点数 边数 1 可作为检验连通图是否包含回路的简便方法。 1.有根树 （通常简称 “树” ） 自由树到有根树（或称树）的转换。如下图所示。,h,g,f,i,有环图,图中，f, h, i, g, f 是一个环。,基本数据结构回顾：自由树转换为有根树,自由树到有根树（树）的转换： 任选自由树中的一个顶点作为根，根常常置于树的顶层（0层），邻接 根的顶点置于下面一层（1层），依此类推。如此形成一种层次结构， 用以描述具有层次关系的对象集合。至于哪个顶点作为根，取决于实际 应用中各顶点所具有的层次关系，如企业的组织架构图所固有的上下级 层次关系（领导关系，平级协作关系）。,概念：祖孙节点，父子节点，兄弟节点，叶节点，入度，出度。 顶点 c 的深度：从根到 c 的路径长度。 （2） 树的高度：从根到叶节点的最长路径长度。（3）,自由树,有根树,问：g, f 节点是兄弟节点吗？,基本数据结构回顾：有序树,2.有序树 有序树是一棵有根树，树中每一顶点（节点）的所有子节点都有序。 有序：树的左右节点排列位置有序。 二叉树：所有的子节点都不超过两个。二叉树只有左右两个子节点。 二叉查找树：或称二叉检索树，设任何一个节点值为K，该节点 左子树 的任意节点值都 K，右子树 的任意节点值都K。,9,5,10,1,4,7,12,二叉查找树及存储结构,基本数据结构回顾：有序树表示,树在计算机中的表示：（存储结构） 方法一：一个父节点和若干兄弟节点的指针。 特点：若不同节点的子节点数相差较大，该法不很好。【 理由？】 方法二：转化为有序二叉树表示，称为关联二叉树。 先子女后兄弟法：左指针指向第一个左子节点，右指针指向其兄弟。,data,pt_2,pt_3,pt_n,关联二叉树,基本数据结构回顾：关联二叉树,关联二叉树,原有根树,先子女后兄弟表示法,基本数据结构回顾：集合,集合与字典 1. 集合的概念： 互不相同的集合元素的无序组合（可以为空）。 2. 集合的表示： 元素列表法：用元素的列表来定义一个特定集合，如 S = 2, 3, 5, 7 特性表示法：指出集合元素满足的特性，如 S = n: n 为质数且 n 10 3. 常见的集合运算： （1）检查一个给定项是否为集合的成员（该项是否在集合元素中）； （2）求两个集合的并集； （3）求两个集合的交集。 4. 集合在计算机中的实现： （1）位向量法：如果 U 具有 n 个元素，那么 U 的任何子集 S 能用一个 长度为 n 的位串表示，称为位向量。如 U = 1, 2, 3, 4, 5, 6, 7, 8, 9 那么 S = 2, 3, 5, 7 用位向量表示为 011010100, 这种集合实现法 能够实现非常快速的标准集合运算，代价是耗费存储空间。,基本数据结构回顾：集合与字典,（2）线性列表法：用线性列表结构来实现集合如数组或链表。（常用） 集合与列表概念上的区别： * 集合不能包含相同的元素，而列表可以。为绕开集合元素唯一性问题， 引入多重集或包的概念，它们都可以包含重复元素。 * 集合是元素的无序组合，所以改变元素在集合中的位置并不改变集合。 列表定义为元素的有序组合，元素位置的改变导致列表改变。实际中 这个问题并不重要，据应用情况，维护线性表的有序性可能是必要的。 5. 字典的概念 能够实现对集合元素的添加、删除、查找三种操作的数据结构。 实现字典的方法有多种，例如从简单的数组实现（有序或无序的）到 类似散列法和平衡查找树等复杂技术。,算法效率分析框架,算法效率分析框架 本节将概要地描述一个分析算法效率的一般性框架。 时间效率指出算法运行得有多快；空间效率关心算法需要的额外空间。 目前，随着计算机硬件技术的飞速发展，空间效率已不是关心重点。 因此，我们主要关心的是时间效率。 输入规模的度量：（问题规模） 一个显而易见的事实：几乎所有的算法，对于更大规模输入都需要运行 更长的时间（即算法耗费的时间随着输入规模的增大而增加） 。例如： 1. 更大的数组排序需要花费更多的运行时间； 2. 更大的矩阵相乘需要花费更多的运算时间。 因此，采用一个以算法输入规模 n 为参数的函数，来研究算法效率就是 非常合乎逻辑的。 输入规模的选择问题： 在大多数情况下，选择这样一个参数是非常直接的。例如，对于排序、 查找以及其他大多数与列表相关的问题来讲，这个参数就是列表长度； 对于 n 次多项式求值问题，这个参数是多项式次数或者系数个数。,输入规模的选择,当然，有些情况下，怎样选择输入规模参数是有差别的。例如计算两个 n 阶矩阵的乘积，有两种度量输入规模的方法： 第一种方法：选择矩阵的阶 n ； 第二种方法：选择参与乘法运算的所有元素个数。 第二种方法更具一般性，适用于非方阵。 对于选择不同的输入规模，其算法效率在含义上有所差别。 选择输入规模参数的合适量度，会受到算法操作细节的影响。例如： 对于一个检查文字拼写的算法，如果算法要求对每个字符都要检查， 那么应该用字符数作为输入规模度量；如果算法操作的是单词，那么 选择单词数作为输入规模的度量。 若算法与数字特性（数字的大小）相关，那么在度量它的输入规模时， 计算机科学家倾向于选择数字的二进制位数作为输入规模的度量。,时间效率的度量,运行时间的度量： 接下来考虑运行时间的度量问题。我们为何不选择时间的标准度量单位 （秒、毫秒等）来度量算法的运行时间呢？其理由如下： 1. 它依赖于特定计算机的运行速度； 2. 它依赖于实现算法的代码质量；（程序员编程的水平问题） 3. 它依赖于编译器的好坏；（编译成机器码的质量，即指令条数） 4. 它还依赖于一些其他问题如操作系统的调度策略等。 鉴于此，希望找到一个不依赖于上述因素的时间度量。 问：是否统计算法的每步操作执行次数来作为算法的时间效率度量呢？ 答：无此必要且较困难。一个算法中有许多操作，决定算法时间效率的 是那些很耗费时间的操作步，因此只需关心这些操作即可评价一个算法 时间效率，这些最关键的操作步称为基本操作，它们对算法执行时间的 占用最大（基本操作即算法中最费时的操作）。所以，用基本操作执行 次数来作为时间效率的度量。,基本操作的选取,基本操作的选取例： 大多数排序算法是通过比较排序元素（键）来进行工作，因此它的基本 操作应选为键的比较操作，即算法中键的比较次数。 矩阵乘法（或多项式运算）需完成两种操作：乘法和加法。对多数机器 而言，乘法比加法更耗费时间，所以选取乘法为基本操作。 在定义了算法的输入规模 n 和基本操作后，我们就可以建立起一个算法 时间效率的分析框架：对输入规模为 n 的算法，通过统计其基本操作的 执行次数来度量算法的时间效率。（时间耗费 T 为输入规模 n 的函数） 分析框架的应用： 设 t 为算法的一个基本操作在特定机器上的执行时间，C(n) 为该算法需 执行的基本操作数。用下式来估计该算法在该机器上的运行时间：,忽略了非基本操作执行时间,问：为什么用约等于符号？,分析框架的应用例,分析框架的应用例： 根据上式，我们可以回答以下问题： 1 若某算法运行在一台比现在机器快10倍的机器上，此算法运行多快？ 答：10倍。（t 增加10倍，C(n)不变） 2 设 ，若输入规模翻倍，该算法运行时间如何变化？,（n 不是太小如 n = 100）,不考虑每个操作步在机器上具体的执行时间 t ，则时间耗费即为：,时间耗费即为基本操作数，为输入规模n的函数。,n的一次、二次函数分别称线性、二次增长率。2n 称指数增长率。,增长次数（增长率）,增长次数（增长率） 基本操作数（时间耗费）是输入规模 n 的函数，记为T(n) 。T(n) 随着 n 次数的增加而增加。函数值T(n) 增加快慢，决定于这个增长函数特性； 也就是说，线性增长函数的函数值增加较慢，二次增长函数增加较快， 指数增长函数最快。因此，我们最关心的就是函数的增长率，它决定了 算法的时间耗费（效率）。若输入规模 n 很小，无论是高效的算法还是 低效的算法，时间耗费差距不明显，所以算法分析针对大规模输入。,增长函数表：对于算法分析具有重要意义的函数值（近似值）,算法效率算例,算法的最优、最差、平均效率 前述已知，我们用输入规模 n 的函数 T(n) 来度量算法的效率。若T(n) 随 n 增长快，则算法效率较差；若T(n) 随 n 增长较慢，则算法效率更好。 这里，没考虑算法效率与特定输入的关系。诸多算法的效率不仅与规模 有关，且与特定的输入有关。下面以顺序查找算法为例： - 【 名称 】顺序查找 【 要求 】在列表中查找一次给定项（查找键），该列表有 n 个元素。 【 算法 】从列表头开始，逐个比较列表中元素，直到发现匹配查找键的 元素或者到达列表尾为止（没找到）。 【 分析 】 1. 很明显，该算法的执行效率与查找键在列表中的位置有密切关系。 2. 若查找键位于表头（第一个元素），该算法只比较一次。最优效率 3. 若查找键位于表尾（最末元素）或不存在，该算法将比较 n 次。最差 4. 若查找键位于表中间，该算法比较次数不固定。平均效率 - 通过上述例子，引入最佳、最差和平均效率的概念。,最优、最差效率,1 最差效率：（最为关注） 当输入规模为 n 时，算法在最坏情况下的效率。此时，相对于其他规模 为 n 的输入，该算法运行时间最长（最慢）。 最差效率的确定：原理上讲，首先对算法作一个分析，看看在规模 n 的 所有可能输入中，那种输入会导致基本操作数 C(n) 达到最大值，计算 这个最差值 Cworse(n)。后面讲到，通过确定算法运行时间的上界，分析 最坏情况为算法效率提供一个非常重要的信息。也即，对于任何规模 n 的实例来讲，它保证算法运行时间不会超过最坏输入情况下的运行时间 Cworse(n)。（最差效率分析的价值） 顺序查找： Cworse(n) = n 2 最优效率： 当输入规模为 n 时，算法在最优情况下的效率。此时，相对于其他规模 为 n 的输入，该算法运行时间最短（最快）。顺序查找： Cbest (n) = 1 最优效率分析的价值：远不如最差效率分析重要，因不能指望每次输入 都是最优输入。但它对算法的的选择有指导意义， 例如：某算法在有序 列表情况下效率很高，对于基本有序的输入数据，该算法可以获得接近 最优输入的效率，实际中可考虑选择该算法。重要的是，如果一个算法 的最优效率都不能满足实际需要，可立即抛弃该算法。,平均效率,3 平均效率 无论是最优还是最差效率，都不能提供这样一种必要信息：在随机输入 情况下，该算法具有怎样的行为（时间耗费）。为此，引入平均效率 。 平均效率分析要比最差和最优效率分析困难很多。以后讨论平均效率时 都引用其已知的推导结果。对推导有兴趣的同学，请查阅有关书籍。 平均效率分析的价值： 有许多重要算法的平均效率比它们过于悲观的最差效率要好很多。所以 如果没有平均效率分析的话，我们会错失不少重要的算法。显然，我们 不能通过求最优和最差效率平均值的方法来求平均效率。 平均效率分析的直接法： 1 将输入分为几种类型（可能的话），目的是使得对于同种输入类型的 实例，具有相同的基本操作数。 2 得到或者假设各类输入的概率分布，以推导出基本操作的平均次数。 但各类输入的概率模型往往又难以验证，虽然它可能很合理。,顺序查找算法的平均时间效率,顺序查找算法的平均时间效率： 假设：(1) 成功查找的概率是 p (0p1)，查找不成功的概率是 1- p； (2) 对任意第 i 次查找，第一次成功匹配（查找成功）发生在列表第 i 个 位置的概率相同，即查找键位于列表任一位置上的概率相同 1/n 。基于 假设，在列表任一位置上查找成功的概率为 p(1/n)（甚至可进一步假设 p=0.5）。若查找成功的位置为 i ，算法做的比较次数（基本操作）为 i 次，考虑成功查找概率，比较次数为 p(i/n)；若查找不成功，算法做的 比较次数为 n（列表全部查找一遍），考虑不成功查找概率，比较次数 则为 n(1-p)。因此，算法平均效率：,统 计 平 均,摊销效率,4 摊销效率 它并不适合于算法的单次运行，而应用于算法对同样数据的多次运行。 我们知道，在有些情况下单次运行的时间代价可能比较昂贵，但 n 次 运行的总时间花费明显低于单次运行的最差效率乘以 n ，因此我们把 最差效率的高成本摊到各次运行中去，即摊销效率。该做法与商业中 把固定资产成本按其使用年限摊销到整个序列（各年）中的做法一致。 通常，具备这种运行特性的算法是在一定程度上的具有“智能”的算法， 通过“学习”获得“知识”累积，再运用知识库中的有关知识对算法下次 如何执行提供指导，从而提高以后运行的效率。一个例子：汉字拼音 输入法中的动态词频调整算法。它统计不同用户对某些字词的使用率 （学习积累过程），来动态调整这些字词下次出现的先后顺序，高频 先现，达到减少用户翻阅时间的目的，提高了该算法的执行效率。 - 后续章节中，除非专门说明，都将最差情况下时间耗费的极限作为算法 的时间耗费，称时间复杂性或时间效率。求解过程称为时间渐进分析。,渐进符号,渐进符号和基本效率类型 上节指出，效率分析主要关心的是一个算法的基本操作数随问题规模的 增长率（增长次数），即问题规模 n 变大情况下，该算法的基本操作数 增长的快慢（它是规模 n 的函数增长函数）。为了对增长函数作出 比较和归类，通常使用三种符号：O,(theta). 下面就这些符号先作一个非正式介绍（便于理解）。 T(n) 和 g(n) ：定义在自然数集合上的任意非负函数（n取自然数）； T(n) ：算法的运行时间函数（常用基本操作数增长函数 C(n) 表示）； g(n) ：与增长函数作比较的函数。 非正式介绍 O(g(n) ：增长次数小于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n) 是增长函数集的上界。例如：,上界符号,(g(n) ：增长次数大于等于g(n)（包括其常数倍，n 趋于无穷大）的 函数集合。即 g(n) 是增长函数集的下界。例如： (g(n) ：增长次数等于g(n)（包括其常数倍，n 趋于无穷大）的函数 集合。即 g(n) 与增长函数集同阶（相同的增长率）。例如： 上界符号 O （最常用） 定义：把函数T(n)包含在O(g(n)中， 记为T(n)O(g(n)；它成立的条件 是：对于足够大的 n，T(n) 的上界 由g(n)的常数倍决定。即存在正数 c 和非负整数 n0，使得下式成立：,下界符号,证明： 证一： 据定义选取： 证二： 据定义选取： 下届符号 定义：把函数T(n)包含在O(g(n)中， 记为T(n)(g(n)；它成立的条件 是：对于足够大的 n，T(n) 的下界 由g(n)的常数倍决定。即存在正数 c 和非负整数 n0，使得下式成立：,规模,增长函数,n0 之前情况无关紧要,下界,最佳效率分析,同阶符号,同阶符号 定义：把函数T(n)包含在O(g(n)中， 记为T(n)(g(n)；它成立的条件 是：对于足够大的 n，T(n) 的下界 和上界均由g(n)的常数倍决定。即 存在正数 c 和非负整数 n0，使得： 例：证明 证：注意到 上界情况： 下界情况：,渐进符号的有用性质,渐进符号的有用性质（1、2、3 证明从略） 性质1： 性质2： 性质3： 性质4： 性质4的价值：（证明见下页） 某些算法是由两个（以上）执行部分组成，性质4指明：该算法的整体 效率由具有较大增长率的部分决定，即它效率最差的部分。举例如下： 数组中特定元素的查找算法：第一部分，用某种已知的排序算法对数组 排序，得到有序数组；第二部分，对有序数组从头至尾扫描，比较是否 与指定元素相等。若排序部分增长函数为0.5n(n-1)O(n2)；第二部分的 增长函数为 nO(n)，那么，算法的整体效率为T(n) O(n2)。,渐进符号性质4的证明,性质4的证明：,利用极限比较增长率,利用极限比较增长率： 此法常用来比较两个特定增长函数的增长率，简便。它根据极限定义， 对两个函数的比值求极限，以判定哪个函数增长更快。,例1：比较0.5n(n-1)和n2的增长率。（或证明: 0.5n(n-1)(n2)）,利用极限比较增长率例,例2：,例3：,渐进效率的基本类型,渐进效率的基本类型,非递归算法分析,非递归算法的效率分析（很常用） 本节将系统地运用前节的通用框架来分析非递归算法的效率。先从一个 简单的算法开始，示范这类算法分析的步骤。 例1：从 n 个元素列表中查找最