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

1、作者：（美）作者：（美）anany levitin 译者：潘彦译者：潘彦出版社：清华大学出版社：清华大学丛书名：国外经典教材丛书名：国外经典教材 计算机计算机 科学与技术科学与技术定价：定价： 45.00￥市场价：市场价：36.00￥w 为什么学习算法为什么学习算法： david harel 在在算法：计算的灵魂算法：计算的灵魂中的描述：中的描述： 对于一个即将从事计算机专业的人士来说，学习算法都是必要的，对于一个即将从事计算机专业的人士来说，学习算法都是必要的， 了解计算领域中不同问题的一系列标准算法，并且具备设计新算法和了解计算领域中不同问题的一系列标准算法，并且具备设计新算法和 分析算法

2、效率的能力。分析算法效率的能力。 随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和随着计算机应用领域（工作和生活）的不断拓展，需要不断地学习和 研究算法。研究算法。w 算法应用领域例算法应用领域例： （1）工作方面：）工作方面：ai（人工智能）、（人工智能）、pr（模式识别）算法的研究。（模式识别）算法的研究。 （2）生活方面：机器博弈算法的研究（象棋、围棋等）。）生活方面：机器博弈算法的研究（象棋、围棋等）。w 算法设计与数据结构算法设计与数据结构： 数据结构主要关心的是数据结构主要关心的是不同的数据结构不同的数据结构（逻辑的）在计算机解题中的（逻辑的）在计算机解题中的 作用和效

3、率，而算法设计与分析关心的是作用和效率，而算法设计与分析关心的是不同的算法不同的算法设计的实用性和设计的实用性和 效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。效率。这使得这两门课程在某种程度上有所重叠，但无法相互代替。算法算法 数据结构数据结构 程序程序 程序功能设计包括：行为设计和结构设计。程序功能设计包括：行为设计和结构设计。 行为设计行为设计：对要解决的问题，提出达到目的所需要实施的步骤序列。：对要解决的问题，提出达到目的所需要实施的步骤序列。 并对这些步骤加以必要细化，用某种方法进行描述，其并对这些步骤加以必要细化，用某种方法进行描述，其 结果就是算法。结果就是算法。

4、算法设计（得到具体问题的算法）算法设计（得到具体问题的算法） 结构设计结构设计：设计算法所需要的高效的数据结构。：设计算法所需要的高效的数据结构。 有了好的算法和数据结构，以某种程序设计语言予以实现有了好的算法和数据结构，以某种程序设计语言予以实现程序程序。w 算法的定义算法的定义： 什么是算法？没有一个公认的用语来描述。针对其含义的基本共识：什么是算法？没有一个公认的用语来描述。针对其含义的基本共识： 图示如下：图示如下：w 算法的几个特点算法的几个特点：（定义的内涵）：（定义的内涵）（1）有穷性：有限时间内完成。如计算）有穷性：有限时间内完成。如计算n！；穷举法解旅行商问题。！；穷举法解旅

5、行商问题。（2）确定性：算法的每一步必须是确定的，不能有两可的解释。）确定性：算法的每一步必须是确定的，不能有两可的解释。（3）可行性：一是每一步必须是有意义的，如约束优化的可行域判定；）可行性：一是每一步必须是有意义的，如约束优化的可行域判定； 二是每一步能够达到预期目的。如求二是每一步能够达到预期目的。如求sinx1的解不可行。的解不可行。（4）输入：输入的值域必须仔细定义；（下例可见）输入：输入的值域必须仔细定义；（下例可见）（5）输出：获得问题的解，无输出的算法是没有意义的。（多种）输出：获得问题的解，无输出的算法是没有意义的。（多种）（6）同一问题求解，可能存在几种不同的算法，执行效

6、率有所差异。）同一问题求解，可能存在几种不同的算法，执行效率有所差异。computer问问 题题算算 法法输输 入入输输 出出 记号一：记记号一：记 m 和和 n 的最大公约数为的最大公约数为 gcd(m, n)，表示能够整除，表示能够整除 m 和和 n （即余数为零）的最大正整数。（即余数为零）的最大正整数。 记号二：记号二：m mod n 表示表示 m 除以除以 n 所得余数。所得余数。w 算法一：欧几里得（公元前算法一：欧几里得（公元前3 3世纪）所著世纪）所著几何原本几何原本解法解法 重复执行下列等式，直到重复执行下列等式，直到 m mod n（余数）等于（余数）等于0：（：（结束条件

7、结束条件） gcd(, n) = gcd( , m mod n) 最后最后 m 的取值就是最大公约数。的取值就是最大公约数。 例如例如 计算如下：计算如下： gcd(, n) = gcd(, 24) = gcd, 12) = gcd(, 0) = （等式）（等式） 欧氏算法的结构化描述欧氏算法的结构化描述： 1. 如果如果 n = 0，返回，返回 m 值为结果输出，值为结果输出，！否则，转！否则，转2步；步； 2. r = m mod n;（赋值）（赋值） 3. m = n, n = r（赋值）（赋值）, 转转1步。（变量交换）步。（变量交换）欧氏算法的伪码描述欧氏算法的伪码描述：（伪码较流程

8、图描述更为先进，建议采用）：（伪码较流程图描述更为先进，建议采用）模块：模块：euclid(m, n)/ 计算计算m,n最大公约数的欧氏算法最大公约数的欧氏算法/ 输入：两个不全为输入：两个不全为0的非负整数的非负整数 m n/ 输出：输出：m，n 的最大公约数的最大公约数while n0 do r m mod n mn n r return （是否会停止循环，输出结果呢）（是否会停止循环，输出结果呢）：设：设 m n，r = m mod n每一次循环（每一次循环（m mod n）后，新）后，新 n 值会变小，但不会变成负数；即值会变小，但不会变成负数；即除数除数 n 大于余数大于余数 r（n

9、 r 0）。余数作为下一轮新）。余数作为下一轮新 n 值（值（nr），），因此因此 ，n 越来越小，最终变成越来越小，最终变成 0。答案：支持。答案：支持。例子：例子：(63, 22)(22, 19) (19, 3)(3,1) (1,0) w 算法二：连续整数检测算法算法二：连续整数检测算法连续检测算法的设计思想：连续检测算法的设计思想：根据定义，根据定义，设，设 t = min m, n 。我们现在。我们现在开始检测开始检测 t 是否为公约数：若是公约数，那么是否为公约数：若是公约数，那么 t 就是最大公约数；否则，就是最大公约数；否则，我们就将我们就将 t 简单地减简单地减1（t = t

10、- 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步；否则，转步

11、；否则，转 4 步；步；3. n 除以除以 t ，若余数为，若余数为0，则输出结果；否则，转，则输出结果；否则，转 4 步；步；4. t 值减值减 1，返回第，返回第 2 步。步。注意，该算法忽略了一些编程时的细节问题：输入值的合法性判定。若注意，该算法忽略了一些编程时的细节问题：输入值的合法性判定。若输入输入 m 或或 n 为为0 值时，算法出错。所以，输入值的值域检查很重要。值时，算法出错。所以，输入值的值域检查很重要。w 算法三：中学计算最大公约数算法三：中学计算最大公约数质因数算法质因数算法算法设计思想：算法设计思想：1. 找出找出 m 所有质因数；（不可以再被整除的因数）所有质因数；

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

13、解决根据上述思想设计算法，尚有两个问题未得到解决：问题问题 1：设计求：设计求 m 和和 n 所有质因数算法；（用各自的质因数数组存放）所有质因数算法；（用各自的质因数数组存放）问题问题 2：设计求两数组公共元素的算法；（有序数组）：设计求两数组公共元素的算法；（有序数组）问题问题 2 的算法较容易设计，请大家自行设计。的算法较容易设计，请大家自行设计。下面考虑问题下面考虑问题 1 的算法设计：求正整数的算法设计：求正整数 n 的全部质因数算法。的全部质因数算法。求正整数求正整数 n 全部质因数的算法全部质因数的算法算法设计：算法设计：给定正整数给定正整数n的全部质因数都不会大于的全部质因数都

14、不会大于n，于是我们可以想办法首先产生，于是我们可以想办法首先产生一个小于一个小于n的质数序列（有序质数数组存放），然后用这些质数去除的质数序列（有序质数数组存放），然后用这些质数去除n，若能整除（余数为若能整除（余数为0），那么该质数就是质因数；否则，就不是质因数。），那么该质数就是质因数；否则，就不是质因数。当质数数组中所有元素都去除过当质数数组中所有元素都去除过n以后，即得到以后，即得到n的全部质因数。现在，的全部质因数。现在，问题发生了转化，即：问题发生了转化，即：，我们姑且称之为质数发生器。我们姑且称之为质数发生器。质数发生器算法设计质数发生器算法设计： 埃拉托色尼（利比亚，公元前埃

15、拉托色尼（利比亚，公元前200年）筛年）筛算法思想：消去法。算法思想：消去法。1. 产生一个产生一个2n的连续整数有序序列（小到大）作为候选质数，的连续整数有序序列（小到大）作为候选质数，k = 1；2. kk + 1，消去（丢弃）序列中为，消去（丢弃）序列中为 k 的倍数的数（整除余数判定）；的倍数的数（整除余数判定）；3. 避免重复消去：如避免重复消去：如4，在消去，在消去 2 的倍数时已被消去，消去的倍数时已被消去，消去3的倍数后，的倍数后， 直接消去直接消去5的倍数，跳过的倍数，跳过 k = 4 这轮的消去；这轮的消去；6，8 等也如此。理由？等也如此。理由？ 4的倍数肯定是的倍数肯定

16、是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 3 5 7 9 11 13 15 17 19 21 23 252 5 7 11 13 17 19 23 252 3 5 7 11 13 17 19 23 2 3 5 11 13 17 19 23进行到消去进行到消去7的倍数时，已没有要消去的数，消去停止，输出结果。的倍数时，已没有要消去的数，

17、消去停止，输出结果。编程实现上述算法时，数据结构需要仔细考虑。这里数据结构问题就是编程实现上述算法时，数据结构需要仔细考虑。这里数据结构问题就是设计多少个一维数组来存放算法的输入数据、中间数据、输出数据。设计多少个一维数组来存放算法的输入数据、中间数据、输出数据。比如，可设计一种简单方案：比如，可设计一种简单方案：1. 用一维数组用一维数组 inn-1 存放存放2n的整数（小到大序）；的整数（小到大序）；in0 = 22. 从从 ini = k 开始的每一轮开始的每一轮(i)消去时，将数组中该轮消去时，将数组中该轮k的倍数数置的倍数数置0。 后续消去时，若后续消去时，若 ini = k = 0

18、，则跳过消去该，则跳过消去该k的倍数，避免重复。的倍数，避免重复。理解问题理解问题了解设备性能了解设备性能决定计算方法：决定计算方法：精确的或近似的解法精确的或近似的解法确定数据结构确定数据结构考虑算法设计技术考虑算法设计技术设计算法设计算法正确性证明正确性证明分析算法分析算法根据算法写代码根据算法写代码算法：算法：。解决方案本身不是问题的答案，而是获得答案解决方案本身不是问题的答案，而是获得答案的精确指令。正是因为强调这个精确的结构化的精确指令。正是因为强调这个精确的结构化过程，使得计算机科学与其他学科特别是理论过程，使得计算机科学与其他学科特别是理论数学区别开来。数学区别开来。 这是实践中

19、设计一个算法前必须做的第一件事情，即完全理解清楚该这是实践中设计一个算法前必须做的第一件事情，即完全理解清楚该 问题，若有任何疑惑就把疑问提出来，手工处理一些小例子，考虑下问题，若有任何疑惑就把疑问提出来，手工处理一些小例子，考虑下 特殊情况，这是一个不断提问的过程，直到彻底搞透彻问题各方面。特殊情况，这是一个不断提问的过程，直到彻底搞透彻问题各方面。 典型问题典型问题： 有几大类问题会频繁出现于计算机应用中，稍后阐述。如果待解决的有几大类问题会频繁出现于计算机应用中，稍后阐述。如果待解决的 问题属于其中一类，我们就可以用一个已知的算法求解。同时，还须问题属于其中一类，我们就可以用一个已知的算

20、法求解。同时，还须 了解清楚该算法的执行过程和优缺点，这对我们解决问题很有帮助，了解清楚该算法的执行过程和优缺点，这对我们解决问题很有帮助， 特别是有几个算法可供选择时。特别是有几个算法可供选择时。 输入问题输入问题： 算法的一个输入，确定了该算法所解问题的一个算法的一个输入，确定了该算法所解问题的一个实例实例。严格确定算法。严格确定算法 处理的实例范围（边界检查）非常重要。如果这一步有所疏忽的话，处理的实例范围（边界检查）非常重要。如果这一步有所疏忽的话， 将可能导致算法对大多数输入能正确处理，但在遇到某些将可能导致算法对大多数输入能正确处理，但在遇到某些“边界值边界值”时时 就出错，甚至使

21、系统彻底崩溃掉。因此，一个正确的算法，能够处理就出错，甚至使系统彻底崩溃掉。因此，一个正确的算法，能够处理 “所有的所有的”、“合法的合法的” 输入。（算法没有限制的输入即为合法输入）输入。（算法没有限制的输入即为合法输入）w 串行算法串行算法（顺序算法）（顺序算法） 今天使用的大多数算法依然注定要靠运行于冯今天使用的大多数算法依然注定要靠运行于冯诺伊曼机器上的代码来诺伊曼机器上的代码来 实现。这种计算机体系结构的重点在于实现。这种计算机体系结构的重点在于（random-access machine, ram）。它最主要思想是：指令逐条执行，每次执行一步）。它最主要思想是：指令逐条执行，每次执

22、行一步 操作。相应地，设计运行于这种机器上的算法即串行（顺序）算法。操作。相应地，设计运行于这种机器上的算法即串行（顺序）算法。w 并行算法并行算法 设计运行于并行计算机上的算法即并行算法。并行计算机可以在同一设计运行于并行计算机上的算法即并行算法。并行计算机可以在同一 时间执行多条指令，即并行计算。这里面包含两层意思：一是计算机时间执行多条指令，即并行计算。这里面包含两层意思：一是计算机 体系结构上的并行（硬件），一是算法本身的并行运算（软件）。在体系结构上的并行（硬件），一是算法本身的并行运算（软件）。在 可以预见的将来，学习可以预见的将来，学习ram模型下算法设计与分析的经典技术仍然是模

23、型下算法设计与分析的经典技术仍然是 算法学的基石。算法学的基石。w 计算速度和存储容量计算速度和存储容量： 绝大多数计算机学家倾向于以一种独立于特定机型的方式研究算法，绝大多数计算机学家倾向于以一种独立于特定机型的方式研究算法， 这是科学研究。若是实用工具，设计的算法取决于具体问题。如海量这是科学研究。若是实用工具，设计的算法取决于具体问题。如海量 数据、实时性要求等，这时需要意识到计算速度和存储容量问题。数据、实时性要求等，这时需要意识到计算速度和存储容量问题。w 选择近似算法的两方面原因：选择近似算法的两方面原因： 1. 无法求精确解无法求精确解。例如：（参阅。例如：（参阅计算方法计算方法

24、有关书籍）有关书籍） 1）多种解非线性方程（超越方程或高次方程）的近似算法。）多种解非线性方程（超越方程或高次方程）的近似算法。 如折半查找法，如折半查找法，0.618法（黄金分割法），牛顿切线法等等。法（黄金分割法），牛顿切线法等等。 2）数值积分法。诸如：）数值积分法。诸如： 找不到原函数的定积分，无法精确积分；被积函数是表格函数找不到原函数的定积分，无法精确积分；被积函数是表格函数 即离散数据点的定积分。算法如矩形法，梯形法，辛普森积分，即离散数据点的定积分。算法如矩形法，梯形法，辛普森积分， 高斯积分等。高斯积分等。 3）数值微分法。用差分近似微分，如）数值微分法。用差分近似微分，如5

25、点差分法等。点差分法等。 4）插值与拟合。插值曲线未知或理论公式未知（得经验公式）插值与拟合。插值曲线未知或理论公式未知（得经验公式） 2. 问题复杂性问题复杂性： 由于某些问题固有的复杂性，用精确算法求解的时间耗费是不能够由于某些问题固有的复杂性，用精确算法求解的时间耗费是不能够 接受的，如旅行商问题的精确求解：穷举法找接受的，如旅行商问题的精确求解：穷举法找 n 个城市之间的最短个城市之间的最短 巡回路径问题。巡回路径问题。 有些算法对数据结构要求不高，但有些算法与数据的构造和重构有着有些算法对数据结构要求不高，但有些算法与数据的构造和重构有着 紧密的联系。面对一个实际问题，决定采用何种数

26、据结构描述问题，紧密的联系。面对一个实际问题，决定采用何种数据结构描述问题， 决定了设计不同的算法，对算法设计难度和执行效率有着重要影响。决定了设计不同的算法，对算法设计难度和执行效率有着重要影响。 比如，串结构存储，树结构存储，图结构存储对后续算法研制的难度比如，串结构存储，树结构存储，图结构存储对后续算法研制的难度 和时空复杂性起着决定性作用。如串的查找，树的查找，图的查找；和时空复杂性起着决定性作用。如串的查找，树的查找，图的查找； 串的匹配，树的匹配，图的匹配。有一些算法就是针对某种数据类型串的匹配，树的匹配，图的匹配。有一些算法就是针对某种数据类型 设计的。例如，解超大型线性方程组问

27、题。由于受计算机内存设计的。例如，解超大型线性方程组问题。由于受计算机内存ram 容量限制，不能在内存中定义一个完整的系数矩阵，数据部分存放于容量限制，不能在内存中定义一个完整的系数矩阵，数据部分存放于 外存（硬盘）上，不断的调入、检索、覆盖、计算、写入等。外存（硬盘）上，不断的调入、检索、覆盖、计算、写入等。 算法设计技术算法设计技术 是用算法解题的是用算法解题的，用于解决，用于解决 。（有时也称。（有时也称“策略策略”或或“范例范例”） （learning such techniques is akin to learning fish as opposed to being given

28、a fish caught by somebody esle）w 自然语言自然语言 自然语言固有的不严密性，要简单清晰地描述算法变得非常困难。自然语言固有的不严密性，要简单清晰地描述算法变得非常困难。w 结构化文字结构化文字（较流行的描述法之一）（较流行的描述法之一） 如前述的欧氏算法描述。如前述的欧氏算法描述。w 流程图流程图 早期占有统治地位，现已过时，只能在早期教材中找到踪迹。主要是早期占有统治地位，现已过时，只能在早期教材中找到踪迹。主要是 因为其在描述算法时非常不方便。因为其在描述算法时非常不方便。w 伪代码伪代码（较流行的描述法之一）（推荐采用）（较流行的描述法之一）（推荐采用）

29、伪码是自然语言和类编程语言的一种混合物，它比自然语言更精确，伪码是自然语言和类编程语言的一种混合物，它比自然语言更精确， 生成的算法描述更为简洁。现今，计算机科学家们并没有对伪码形式生成的算法描述更为简洁。现今，计算机科学家们并没有对伪码形式 达成某一种共识，而是作者一种达成某一种共识，而是作者一种“”。幸运的是，这些方言在彼。幸运的是，这些方言在彼此此 之间非常相似，使得任何熟悉一门现代编程语言的人都能完全理解。之间非常相似，使得任何熟悉一门现代编程语言的人都能完全理解。 当代计算机还不能将伪码直接当代计算机还不能将伪码直接“输入输入”计算机，需要把伪码算法用特计算机，需要把伪码算法用特定定

30、 编程语言写成程序编程语言写成程序算法的实现。（翻译过程：伪码算法的实现。（翻译过程：伪码算法）算法）w 算法的正确性算法的正确性 对于一个对于一个“合法输入合法输入”，该算法都能在有限时间内输出要求的结果。，该算法都能在有限时间内输出要求的结果。 比如：计算最大公约数的欧氏算法的正确性基于如下等式的正确性：比如：计算最大公约数的欧氏算法的正确性基于如下等式的正确性： gcd(m, n) = gcd(n, m mod n) 现在轮到证明这个等式的正确性了。该算法的每一次循环，现在轮到证明这个等式的正确性了。该算法的每一次循环，n 值将会值将会 变小的观察结果，以及算法会在变小的观察结果，以及算

31、法会在 n 变为变为 0 时停止的事实。时停止的事实。w 算法正确性证明方法算法正确性证明方法 某些算法的正确性证明非常简单，但某些算法证明却可能十分复杂。某些算法的正确性证明非常简单，但某些算法证明却可能十分复杂。 一般采用数学归纳法，因为算法的迭代过程原本就提供了这种证明所一般采用数学归纳法，因为算法的迭代过程原本就提供了这种证明所 需要的一系列步骤。值得一提的是，用特定输入来追踪算法的执行是需要的一系列步骤。值得一提的是，用特定输入来追踪算法的执行是 很有意义的，但它并不能证明算法的正确性；反之，可通过列举反例很有意义的，但它并不能证明算法的正确性；反之，可通过列举反例 方法发现算法的不

32、正确，再次设计或改进算法。方法发现算法的不正确，再次设计或改进算法。w 近似算法近似算法 常常证明该算法的常常证明该算法的误差误差不超出我们预定的范围。（收敛性）不超出我们预定的范围。（收敛性） 事前误差估计法、事后误差检验法（收敛算法的迭代停止条件）。事前误差估计法、事后误差检验法（收敛算法的迭代停止条件）。w 算法的效率算法的效率： 空间效率和时间效率，即时空效率。（后面讲解算法效率分析）空间效率和时间效率，即时空效率。（后面讲解算法效率分析） 时空效率即运行算法所需要耗费的空间（时空效率即运行算法所需要耗费的空间（ram）和时间。随着计算机）和时间。随着计算机 硬件系统的飞速发展，空间效

33、率不象早期要求的那样高，而着重考虑硬件系统的飞速发展，空间效率不象早期要求的那样高，而着重考虑 时间效率。一般来说，宁愿以空间换时间。时间效率。一般来说，宁愿以空间换时间。w 算法的简单性算法的简单性： 简单就象简单就象“美丽美丽”一样，很大程度上取决于审视者的眼光。（主观性）一样，很大程度上取决于审视者的眼光。（主观性） 简单性仍然是需要努力实现的一个算法特性。因为，简单的算法更易简单性仍然是需要努力实现的一个算法特性。因为，简单的算法更易 理解和实现（理解和实现（软件工程软件工程），相应的程序也往往包含较少的），相应的程序也往往包含较少的bug。 w 算法的一般性算法的一般性：包含解决问题

34、的一般性、接受输入的一般性：包含解决问题的一般性、接受输入的一般性 解决问题的一般性：比如判断两个整数是否互质。可以设计一个一般解决问题的一般性：比如判断两个整数是否互质。可以设计一个一般 算法：计算两个整数的最大公约数，然后检验其是否等于算法：计算两个整数的最大公约数，然后检验其是否等于1。 接受输入的一般性：即输入的范围。考虑：在当前问题所可能涉及的接受输入的一般性：即输入的范围。考虑：在当前问题所可能涉及的 范围内即可，不必过于追求扩大输入范围。比如实数域求解的问题，范围内即可，不必过于追求扩大输入范围。比如实数域求解的问题， 没必要扩大到复数域，除非当前问题要求那样做。没必要扩大到复数

35、域，除非当前问题要求那样做。在算法领域中，有一些问题吸引研究人员的特殊关注。大体来讲，要么在算法领域中，有一些问题吸引研究人员的特殊关注。大体来讲，要么是问题具有实用上的重要性，要么是问题具有一些重要的特征：是问题具有实用上的重要性，要么是问题具有一些重要的特征：后续课程将用这些问题来说明不同的算法设计技术和算法的分析方法。后续课程将用这些问题来说明不同的算法设计技术和算法的分析方法。w 问题问题：按照升序（或降序）重新排列给定数表中的数据项。：按照升序（或降序）重新排列给定数表中的数据项。w 应用例应用例： 1）学校维护的学生信息记录；）学校维护的学生信息记录； 2）图书馆维护的图书信息记录

36、；）图书馆维护的图书信息记录； 3）公司维护的员工信息记录；）公司维护的员工信息记录；w 键键： 对记录排序时，我们需要选取一段特定信息（数据库中叫字段）作为对记录排序时，我们需要选取一段特定信息（数据库中叫字段）作为 排序依据，这段特定信息称为排序依据，这段特定信息称为键键。w 为什么需要排序列表为什么需要排序列表 答案：便于查找。这就是为什么字典、电话簿、班级名册是排序的。答案：便于查找。这就是为什么字典、电话簿、班级名册是排序的。 在实际的诸多算法中，排序是一个辅助步骤。在实际的诸多算法中，排序是一个辅助步骤。w 排序算法简介排序算法简介： 目前，已研制了几十种不同的排序算法，还在不断开

37、发中。虽然有些目前，已研制了几十种不同的排序算法，还在不断开发中。虽然有些 算法比其他算法更好，但没有一种算法在任何情况下都是最好的解决算法比其他算法更好，但没有一种算法在任何情况下都是最好的解决 方案。有些算法简单，但速度慢；有些算法适合排列驻留在内存中的方案。有些算法简单，但速度慢；有些算法适合排列驻留在内存中的 列表；而有些算法可以用来排列存储于磁盘上的大型文件；有些算法列表；而有些算法可以用来排列存储于磁盘上的大型文件；有些算法 适合于随机输入；而有些算法更适合于基本有序的列表。适合于随机输入；而有些算法更适合于基本有序的列表。w 排序算法的两个特性排序算法的两个特性： 1）稳定的稳定

38、的： 如果一个排序算法保留了如果一个排序算法保留了等值元素在排序前后列表中的相对顺序等值元素在排序前后列表中的相对顺序， 称为稳定的。换句话说，输入列表中包含两个等值元素，它们的称为稳定的。换句话说，输入列表中包含两个等值元素，它们的 位置分别为位置分别为 i 和和 j ， ；在排好序的输出列表中，它们的位置为；在排好序的输出列表中，它们的位置为 i 和和 j，那么，那么 （在前元素仍在前）。这种特性是有用的，如：（在前元素仍在前）。这种特性是有用的，如： 我们有一个按学生姓名字母排序的列表，现在要求按其平均成绩我们有一个按学生姓名字母排序的列表，现在要求按其平均成绩 排序输出。一个稳定排序算

39、法输出的列表将会把排序输出。一个稳定排序算法输出的列表将会把同样成绩同样成绩的学生的学生 仍按其姓名字母序排列。仍按其姓名字母序排列。 2）在位的在位的： 如果一个排序算法除了个别存储单元外，不需要额外的存储空间，如果一个排序算法除了个别存储单元外，不需要额外的存储空间， 则称为在位的。则称为在位的。w 查找查找：从给定集合（或多重集，有几个元素具有相同的值）中找到：从给定集合（或多重集，有几个元素具有相同的值）中找到 一个给定的值，称为一个给定的值，称为。w 多种查找算法多种查找算法： 顺序查找（挨个比较，时间效率较低），折半查找（时间效率极高，顺序查找（挨个比较，时间效率较低），折半查找（

40、时间效率极高， 但要求输入为排序列表）。还有些将原来的集合表示为另一种形式但要求输入为排序列表）。还有些将原来的集合表示为另一种形式 以方便查找，如查找多重索引表。这对大型数据库存取来说，具有以方便查找，如查找多重索引表。这对大型数据库存取来说，具有 重要意义。重要意义。 考虑问题考虑问题：要求开发一个特大型数据记录集的：要求开发一个特大型数据记录集的快速查找快速查找算法。算法。 已知条件已知条件：数千万条记录存放于硬盘上，并可以添加、修改记录。：数千万条记录存放于硬盘上，并可以添加、修改记录。 解决方案解决方案：选择怎样的数据结构和算法。：选择怎样的数据结构和算法。w 串：有字母和数字构成的

41、序列（文本串）。由串：有字母和数字构成的序列（文本串）。由0和和1构成的是位串。构成的是位串。w 串匹配：在给定文本中查找一个给定的串匹配：在给定文本中查找一个给定的“词词”。w 模式识别中的特征串描述、精确匹配与相似匹配问题。模式识别中的特征串描述、精确匹配与相似匹配问题。w 图算法是最古老也最令人感兴趣的问题。图算法是最古老也最令人感兴趣的问题。 不严格定义的话，图是由一些顶点和边相连接（下节严格定义）。不严格定义的话，图是由一些顶点和边相连接（下节严格定义）。 图，可以对广泛的、各种各样的实际应用建模，如交通网络，通讯图，可以对广泛的、各种各样的实际应用建模，如交通网络，通讯 网络，计算

42、机网络，汉字笔画描述等等。网络，计算机网络，汉字笔画描述等等。w 图的基本算法：图的基本算法： 1. 图的遍历算法：如何一次访问图中所有的节点；图的遍历算法：如何一次访问图中所有的节点； 2. 最短路线算法：两个城市之间的最短路线是哪一条；最短路线算法：两个城市之间的最短路线是哪一条； 3. 有向图的拓扑排序：一系列过程的前提条件是一致的还是矛盾的。有向图的拓扑排序：一系列过程的前提条件是一致的还是矛盾的。w 某些图问题的困难：某些图问题的困难： ：找出访问：找出访问 n 个城市的最短路线，每个城市只访问一次。个城市的最短路线，每个城市只访问一次。 ：用最少种的颜色为图中各顶点填色，并保证任何

43、两个：用最少种的颜色为图中各顶点填色，并保证任何两个 邻接顶点的颜色不同。邻接顶点的颜色不同。 ：如何判定两个不同的图是相似的。比如模式识别中用：如何判定两个不同的图是相似的。比如模式识别中用 图描述模式时，识别同一模式的变形模式会产生此问题。图描述模式时，识别同一模式的变形模式会产生此问题。 在给定集合中寻找一个组合对象，如一个排列、一个组合或一个子集在给定集合中寻找一个组合对象，如一个排列、一个组合或一个子集 满足给定的要求，如成本最小化或价值最大化等。从更抽象的角度看满足给定的要求，如成本最小化或价值最大化等。从更抽象的角度看 图填色问题和旅行商问题都是组合问题。图填色问题和旅行商问题都

44、是组合问题。 一般而言，组合问题是计算上最困难的问题，理由：一般而言，组合问题是计算上最困难的问题，理由： 1. 随着问题规模的增大，组合对象的数量增长极快，产生组合爆炸；随着问题规模的增大，组合对象的数量增长极快，产生组合爆炸； 2. 没有一种已知算法在可接受时间内，精确地解决绝大多数此类问题。没有一种已知算法在可接受时间内，精确地解决绝大多数此类问题。 且大多数计算机科学家认为这样的算法并不存在。某些组合问题能且大多数计算机科学家认为这样的算法并不存在。某些组合问题能 用效率较高的算法解决，但我们应把它归于运气和例外。如旅行商用效率较高的算法解决，但我们应把它归于运气和例外。如旅行商 问题

45、的某些算法有时能得到最优结果。问题的某些算法有时能得到最优结果。 两个最经典的计算几何问题。两个最经典的计算几何问题。w 最近对问题：给定平面上最近对问题：给定平面上 n 个点，求距离最近的两个点。个点，求距离最近的两个点。w 凸包问题：求给定点集中所有点包含在内的最小凸多边形。凸包问题：求给定点集中所有点包含在内的最小凸多边形。 这是另一个广泛的应用领域，涉及具有连续性的数学对象问题，如：这是另一个广泛的应用领域，涉及具有连续性的数学对象问题，如： 解方程和方程组（如代数、微分、偏微分、积分），计算定积分，求解方程和方程组（如代数、微分、偏微分、积分），计算定积分，求 函数值等等。对于大多数

46、此类问题，我们只能近似求解。此外，这类函数值等等。对于大多数此类问题，我们只能近似求解。此外，这类 问题一般都要操作实数，实数在计算机内部只能近似表示，对近似数问题一般都要操作实数，实数在计算机内部只能近似表示，对近似数 大量算术操作导致误差积累，严重时使算法失效。所以，在数值算法大量算术操作导致误差积累，严重时使算法失效。所以，在数值算法 的设计和实现时，要注意误差分析和避免误差放大的设计技术。比如的设计和实现时，要注意误差分析和避免误差放大的设计技术。比如 两操作数求和时产生的两操作数求和时产生的“大数吃小数大数吃小数”现象。现象。 问：大数吃小数现象是如何产生的？问：大数吃小数现象是如何

47、产生的？ 算法是对数据的操作，组织数据的特殊方式在算法设计和分析中扮演算法是对数据的操作，组织数据的特殊方式在算法设计和分析中扮演 重要角色，可将重要角色，可将数据结构数据结构定义为相关数据项的组织方式。因此，数据定义为相关数据项的组织方式。因此，数据 结构在算法设计中起重要作用。结构在算法设计中起重要作用。w 线形数据结构线形数据结构 ：n 个个相同数据类型相同数据类型的元素构成的序列，的元素构成的序列，连续存储连续存储在内存中。在内存中。 通过指定数组通过指定数组下标下标就能访问数组的元素。无论位于数组中就能访问数组的元素。无论位于数组中 任何位置，其访问时间都相等，该特性将数组与链表截然

48、任何位置，其访问时间都相等，该特性将数组与链表截然 分开。数组可实现多种其他数据结构，较为突出的是串。分开。数组可实现多种其他数据结构，较为突出的是串。 串来自于字母表中的字符序列，以一个特殊字符来标识串串来自于字母表中的字符序列，以一个特殊字符来标识串 结束。由结束。由 0 和和 1 组成的串称为二进制串或者比特串。串的组成的串称为二进制串或者比特串。串的 常见操作包括计算串的长度，按字典序比较两个串的优先常见操作包括计算串的长度，按字典序比较两个串的优先 顺序，连接两个串等。顺序，连接两个串等。 数据项数据项0 数据项数据项1 数据项数据项2 数据项数据项n-1：由一个或多个称为：由一个或

49、多个称为节点节点的元素构成的序列。每个节点包含的元素构成的序列。每个节点包含 两类信息（域）：数据域和指针域。指针可以是多个，指向表中两类信息（域）：数据域和指针域。指针可以是多个，指向表中 其他元素（用其他元素（用null指针表示该节点没有后继节点）。指针表示该节点没有后继节点）。单链表单链表中中 除了最后节点外，每个节点都包含一个指向下个元素的指针。除了最后节点外，每个节点都包含一个指向下个元素的指针。 为了访问链表中某个特定元素，为了访问链表中某个特定元素， 需要从链表的第一个元素开始，需要从链表的第一个元素开始， 直到访问到该元素为止。因此，访问单链表中元素所需要的时间直到访问到该元素

50、为止。因此，访问单链表中元素所需要的时间 与数组不同，依赖于该元素在链表中的位置。链表的优点是，其与数组不同，依赖于该元素在链表中的位置。链表的优点是，其 节点在内存中不是连续分配的，需要一个才创建一个，不需事先节点在内存中不是连续分配的，需要一个才创建一个，不需事先 固定分配而占用多余的内存，对事先不能预知数据项多少的应用固定分配而占用多余的内存，对事先不能预知数据项多少的应用 特别适合。其常见操作为节点的插入和删除，通过重新连接链表特别适合。其常见操作为节点的插入和删除，通过重新连接链表 指针来实现。另外，尚有扩展结构如双链表、循环链表等。指针来实现。另外，尚有扩展结构如双链表、循环链表等

51、。数据项数据项0数据项数据项1数据项数据项n-1 nullnull 数据项数据项0 数据项数据项1 数据项数据项n-1 null：数据项的插入与删除均在尾端（栈顶）进行操作的列表。：数据项的插入与删除均在尾端（栈顶）进行操作的列表。 在栈中添加一个元素称为进栈（在栈中添加一个元素称为进栈（push），删除栈顶的一个元素），删除栈顶的一个元素 称出栈（称出栈（pop）。该结构按照后进先出（）。该结构按照后进先出（lifo, last-in-first-out） 方式运转。栈，具有众多优点，尤其是对于实现递归算法。方式运转。栈，具有众多优点，尤其是对于实现递归算法。：数据项的插入在列表的一端（队尾

52、）进行，删除在另一端：数据项的插入在列表的一端（队尾）进行，删除在另一端 （队头）进行，分别称为（队头）进行，分别称为入队入队(enqueue) 、出队出队(dequeue) 。因此，。因此， 队列是按先进先出（队列是按先进先出（fifo, first-in-first-out）方式运行。）方式运行。w 图图 按照非正式定义，图可以认为是由平面上的节点（或称顶点）构成的按照非正式定义，图可以认为是由平面上的节点（或称顶点）构成的 集合，某些顶点由边（或称为弧）的线段连接。按照图的正式定义：集合，某些顶点由边（或称为弧）的线段连接。按照图的正式定义： 图图 是一个二元组，由两个集合来定义：一个有

53、限集合是一个二元组，由两个集合来定义：一个有限集合v， 它的元素称为顶点；另一个有限集合它的元素称为顶点；另一个有限集合e，其元素是一对顶点，称为边。，其元素是一对顶点，称为边。 acbdef , , , , ,( , ),( , ),( , ),( ,),( , ),( , ),( ,)va b c d e fea ca db cb fc ed ee f （1）无向图与有向图：）无向图与有向图： 每对顶点之间没有顺序，顶点对每对顶点之间没有顺序，顶点对 (u, v) 和和 (v, u) 是相同的，即边是是相同的，即边是 没有方向的，称为没有方向的，称为无向图无向图。否则，我们说边。否则，我们

54、说边 (u, v) 的方向是从顶点的方向是从顶点 u 到顶点到顶点 v ， 称为称为有向图有向图。（3）完全图：）完全图： 任意两个顶点之间都有边相连的图。任意两个顶点之间都有边相连的图。（4）稠密图：）稠密图： 相对完全图而言，所缺边数较少的图。相对完全图而言，所缺边数较少的图。（5）稀疏图：）稀疏图： 相对完全图而言，所缺边数较多的图。相对完全图而言，所缺边数较多的图。acbdef1. 1. 图的两种表示法图的两种表示法用一个用一个 n n 的布尔矩阵表示具有的布尔矩阵表示具有 n 个顶点的图，图中每个顶点用一行个顶点的图，图中每个顶点用一行和一列表示。若从第和一列表示。若从第 i 个顶点

55、到第个顶点到第 j 个顶点有边连接，则矩阵中第个顶点有边连接，则矩阵中第 i 行行第第 j 列元素的值为列元素的值为1；若没有边连接，则该元素值为；若没有边连接，则该元素值为0。000001100010011101010010001110100010abcdefabcdefacbdef每一个顶点用一个邻接链表表示。该链表每一个顶点用一个邻接链表表示。该链表包括了与这个顶点邻接的所有顶点。包括了与这个顶点邻接的所有顶点。cdcfababcdeaecdfbeef 表表头头2. 2. 加权图（带权图）加权图（带权图）概念：加权图是一种给边赋值的图，这些值称为边的权重。概念：加权图是一种给边赋值的图，

56、这些值称为边的权重。应用：比如求交通网或通讯网的最短路径问题。将每个城市定义为应用：比如求交通网或通讯网的最短路径问题。将每个城市定义为 一个顶点，用边连接两个城市，边的权重表示两个城市的距离。一个顶点，用边连接两个城市，边的权重表示两个城市的距离。表示：邻接矩阵或邻接链表都可以表示加权图。表示：邻接矩阵或邻接链表都可以表示加权图。abcd157240510507417020420abcdabcd,5,1,5,7,4,1,7,2,4,2abcbcadcdabdbc2. 2. 路径和环路径和环图的诸多特性中，有两个常用特性：连通性和无环性。均基于路径。图的诸多特性中，有两个常用特性：连通性和无环

57、性。均基于路径。从起始顶点出发到终止顶点结束的一个顶点序列。从起始顶点出发到终止顶点结束的一个顶点序列。一条路径不重复通过该路径上的任一顶点。（仅通过一次）一条路径不重复通过该路径上的任一顶点。（仅通过一次）路径顶点序列中所包含的顶点数减一。（等于边数）路径顶点序列中所包含的顶点数减一。（等于边数）每一对顶点都存在一条路径连接的图。否则，称非连通图。每一对顶点都存在一条路径连接的图。否则，称非连通图。acbdef简单路径：简单路径：a, c, b, f 长度：长度：3acbdef非简单路径：非简单路径：a, c, e, c, b, f 长度：长度：5acbdehgf i左图为非连通图，包括左图

58、为非连通图，包括两个连通的子图，也即两个连通的子图，也即连通分量为连通分量为2。起点和终点都是同一个顶点，且长度大于起点和终点都是同一个顶点，且长度大于 0 的简单路径。的简单路径。不包括回路的图。（包括闭合路径的图或子图，如下）不包括回路的图。（包括闭合路径的图或子图，如下）w 树树概念：连通无回路的图。准确术语：概念：连通无回路的图。准确术语：。森林：若干树的集合。树与树之间不连通。森林：若干树的集合。树与树之间不连通。特点：边数比顶点数少一，即：特点：边数比顶点数少一，即： 可作为检验连通图是否包含回路的简便方法。可作为检验连通图是否包含回路的简便方法。1.1.有根树有根树 （通常简称（

59、通常简称 “” ）自由树到有根树（或称树）的转换。如下图所示。自由树到有根树（或称树）的转换。如下图所示。hgf i图中，图中，f, h, i, g, f 是一个环。是一个环。自由树到有根树（树）的转换自由树到有根树（树）的转换：自由树中的一个顶点作为根，根常常置于树的顶层（自由树中的一个顶点作为根，根常常置于树的顶层（0层），邻接层），邻接根的顶点置于下面一层（根的顶点置于下面一层（1层），依此类推。如此形成一种层次结构，层），依此类推。如此形成一种层次结构，用以描述具有层次关系的对象集合。至于哪个顶点作为根，取决于实际用以描述具有层次关系的对象集合。至于哪个顶点作为根，取决于实际应用中各顶

60、点所具有的层次关系，如应用中各顶点所具有的层次关系，如企业的组织架构图企业的组织架构图所固有的上下级所固有的上下级层次关系（领导关系，平级协作关系）。层次关系（领导关系，平级协作关系）。ichbgadefabchdegfi概念：祖孙节点，父子节点，兄弟节点，叶节点，入度，出度。概念：祖孙节点，父子节点，兄弟节点，叶节点，入度，出度。顶点顶点 c 的深度：从根到的深度：从根到 c 的路径长度。的路径长度。 （2）树的高度：从根到叶节点的最长路径长度。（树的高度：从根到叶节点的最长路径长度。（3）：g, f 节点是节点是兄弟节点吗？兄弟节点吗？2.2.有序树有序树有序树是一棵有根树，树中每一顶点（