算法分析与设计.doc

目录第一章 绪论 31.1 算法的概念 31.2 算法问题求解基础 61.3 重要的问题类型 91.4 基本数据结构 11第二章 算法效率分析基础 162.1 分析框架 162.2 渐进符号和基本效率类型 192.3 非递归算法的数学分析 222.4 递归算法的数学分析 252.5 例：Fibonacci数列※ 27第三章 蛮力法（BRUTE FORCE）和算术问题 333.1 选择排序和冒泡排序 333.2 蛮力字符串匹配※ 353.3 穷举搜索（Exhaustive Search） 363.4基本算术 403.5模算术 423.6素性检测 423.7密码学 42第四章 分治法（DEVIDE-AND-CONQURE） 434.1 主定理（Master Theorem） 434.2 归并排序 444.3 快速排序 464.4 大整数乘法※ 494.5 Strassen矩阵乘法※ 504.6快速傅里叶变换FFT※ 52第五章 减治法（DECRESE-AND-CONQURE） 585.1 插入排序 585.2 深度优先搜索和广度优先搜索※ 595.3 生成组合对象的算法 635.4 二叉搜索（折半查找） 675.5 乘法和乘方问题※ 695.6 Euclid算法分析※ 71第六章 时空权衡（TIME AND SPACE TRADEOFFS）与动态规划（DYNAMIC PROGRAMMING） 726.1 计数排序 726.2 高效串匹配算法※ 736.3 再谈Fibonacci数列 786.4 有向无环图中最短路径※ 796.5 计算传递闭包的Warshall算法和多源最短路径问题的Floyd算法 816.6 矩阵链相乘问题 846.7 最优二叉搜索树※ 866.8 最长递增子序列※ 896.9 编辑距离※ 896.10 背包问题※ 926.11 旅行商TSP问题※ 95第七章 贪心法（GREEDY TECHNIQUES） 997.1 连续背包问题※ 997.2 最小生成树问题（MST，minimum spanning tree） 1027.3 单源最短路径问题的Dijkstra算法 1097.4 Huffman编码 1127.5集合覆盖 118第八章 线性规划（LINEAR PROGRAMMING） 1198.1 线性规划简介 1198.2 求解线性规划问题的单纯形算法 1228.3 网络流问题 1298.4 二部图的匹配问题 1298.5 对偶 1298.6 零和游戏 130第九章 算法能力的极限 1319.1 求算法下界的方法 1319.2 问题归约 1329.3 P，NP和NP完全问题 1349.4 回溯法（Backtracking） 1399.5 分支限界法（Branch-and-Bound） 1419.6 近似算法（Approximation algorithms） 144第一章 绪论1.1 算法的概念算法：解决一个问题的无歧义的指令序列，对合法的输入在有限的时间内可得到需要的输出。

算法的一些特点：这才叫算法n 无歧义性（确定性）：算法的每个步骤必须确定无疑n 有穷性：算法的执行必须有限步终止n 输入的范围：算法只对这指特定问题的算法满足条件的输入有响应 n 正确性：算法应能解决要求的问题n 同一算法的不同表示形式：自然语言、伪代码、高级语言n 同一问题存在的多种算法：设计思想不同，时空性能各异例，求两个正整数m和n的最大公因子的算法算法一 最容易想到的算法——挨个检查Step 1 t = min {m, n}Step 2 如果m除以t的余数为0，转Step 3；否则，转Step 4；Step 3 如果n除以t的余数为0，返回t的值；否则，转Step 4；Step 4 t = t – 1，转Step 2分析：n 上述步骤每一步均确定没有歧义，是一个循环结构程序n 循环执行次数未知，那么它会有限步终止吗？（每次t – 1）n 该算法由自然语言描述n 该算法正确吗？如何证明？算法二 小学数学中讲述的算法Step 1 将m分解质因子；Step 2 将n分解质因子；Step 3 寻找Step 1和Step 2得到的两个质因子连乘积的公共部分（注：若m的分解中质因子p出现了x次，n的分解中p出现了y次，作为公共部分，p应出现min{x, y}次）；Step 4 计算公共部分的连乘积，并将结果返回。

分析：此算法中，如何分解质因子没说明，如何寻找公共部分不清楚，不满足算法的确定性要求，所以严格讲起来不能称为算法，至少有待进一步具体说明！考虑如何具体说明：n 分解质因子需要知道有哪些质数n 寻找公共部分涉及到质因子连乘积的表示形式算法三 Euclid算法（记录于公元前3世纪Euclid所著的Elements）Euclid (m, n)//Input：两个正整数m和n//Output：m和n的最大公因子while n≠0 dor = m mod n m = n n = rreturn m分析：n 上述步骤每一步均确定没有歧义，是一个循环结构程序n 循环执行次数未知，那么它有限步终止吗？（每次n都减小）n 该算法由伪代码描述：伪代码是自然语言和编程语言的混合n 该算法正确吗？如何证明？证明：设函数gcd(m, n)就是采用Euclid算法计算最大公因子的函数则算法的正确性基于两个事实：Ø 若m≠0，则gcd(m, 0)= m Ø gcd(m, n) = gcd(n, m mod n)第一个事实显然易见设d = gcd(m, n)且m = kn + t则存在a，b使得m = ad，n = bd，且a与b互质。

m mod n = t = m – kn = ad – kbd =(a – kb)*d说明d是n和m mod n的公因子，还需说明，b与a – kb互质假设b与a – kb有公因子c即，b = uc，a – kb = vc则a = kuc + vc =(ku + v)*c，m =(ku + v)*cd，n = bd = ucd，由d是m与n的最大公因子得c=1，即b与a – kb互质 ■比较上述三个算法，很明显，Euclid算法形式简单，循环次数少（后面会进行详细分析），所以我们说Euclid算法更高效1.2 算法问题求解基础算法是求解的具体指令，不是解答设计和分析算法的典型步骤：1. 理解问题1) 仔细阅读问题描述2) 手工测试几个例子3) 思考特殊情形4) 分析是否已有该类问题的算法2. 确定计算设备的能力现行的绝多数算法都是基于冯·诺依曼机器模型的，即，随机存储模型，它假定指令依次执行，每次执行一个操作，在这样机器上执行的算法称为sequential算法适合于现在新兴的可同时执行多条操作的计算机的算法，称为并行算法除非对某些本质上复杂、需处理大量数据或者对时间要求很高的问题，无需担心现在计算机的能力！！！3. 选择精确算法还是近似算法1) 存在某些问题不能精确解决，例如求平方根2) 可精确解决的算法难以接受的慢，例如，TSP问题3) 近似算法可以是某些更为复杂的精确算法的组成部分4. 确定合适的数据结构存在某些算法设计方法固有依赖于描述问题的数据结构。

5. 算法设计方法本课程所要解决的主要问题算法设计方法（或策略）是指：从算法上解决问题的通用方法，可适用于不同领域的各种各样的问题学习这些方法的原因：1) 有助于为新问题设计算法，授人以鱼不如授人以渔2) 每门学科都对其研究主题进行分类，算法是计算机科学的基础，有助于根据设计思想对算法进行分类6. 描述算法的方法1) 自然语言描述，如前例中算法一、二2) 伪代码描述，如前例中算法三Euclid算法，无统一格式3) 流程图，只适合于描述很简单的算法4) 某种计算机语言写成的程序7. 证明算法的正确性一旦算法描述清楚，就需要证明其正确性，即，它对每一个合法的输入都可以在有限的时间内得出需要的结果证明算法正确的一个常用方法是：数学归纳法注意：测试几组输入数据的方法虽然简单，但却不足以说明算法正确！不过却可以说明一个算法不正确！8. 算法分析算法应具有的几个品质：本课程所要解决的主要问题1) 正确性2) 效率：时间效率和空间效率第二章详述3) 简洁性：无法用数学定义精确描述，最好给人以美感例，前述的求gcd的算法哪个更简单？简单的算法易于理解，易于编程，通常包含较少的bug，一般也更有效率4) 通用性：同样的效率，解决的问题可适用范围当然越广越好，但是有时通用算法难设计且效率差，或者根本无通用算法例，判定两个正整数是否互质的算法就没有求gcd的通用；二次方程求根公式存在的，但没有任意次方程的求根方法9. 算法编码实现1) 注意程序严格准确的实现算法2) 算法到程序的过渡：算法中假设输入都是合法的，程序中需验证3) 程序的正确性验证的实际方式：测试（testing）。

4) 学习编程技巧，以提高程序效率最优算法（optimality）：不是算法效率的问题，而是算法解决问题的复杂性，即，解决某类问题的任意算法中哪个所付出的代价最少某些问题的最优算法是存在的，比如，通过比较进行排序的最优算法需要进行n log n次比较；但某些看上去简单的问题，还未找到最优算法，例如，矩阵乘法不可判定性(undecidability)：不是说，每个问题均有算法解决（注意，这不同于一个问题没有解，例如，判别式为负的二次方程无实数解）所幸的是，实际计算中的绝大多数问题还是有解决算法的1.3 重要的问题类型后面的章节将以以下问题展开，讨论不同算法的设计技术与分析方法1. 排序我们经常遇到排序问题，比如学校学生按学号排序，学号通常被称为key那么为什么要进行排序？排序使得很多关于列表的问题简单，比如字典中单词的搜索；排序还常作为某些领域重要算法的辅助步骤，比如，在几何算法中当前，已有很多排序算法，在这些算法当中，有些较好的可将任意n个元素通过大约n log2 n比较完成排序，但是没有哪一个通过关键字比较的排序算法能比n log2 n作的更好！排序算法的两个性质：排序是否稳定（保持输入相等元素的相对次序不变）和是否需要大量辅助空间（in place排序）。

2. 搜索（查找）同样，有很多搜索算法，简单的如顺序搜索，快速的如二叉搜索（要求元素已排序），等等由于搜索经常与添加和删除操作联系在一起，所以，需仔细设计数据结构3. 字符串处理※由于所有程序在计算机看来都是字符串，所以此类算法同计算机语言和编译紧密相关此类算法中最特殊的一个——字符串匹配——在给定文本中搜索给定单词，在实际中非常有用4. 图论问题算法中最古老而又吸引人的领域就是图算法图可以看作是由若干结点和若干个连接其中某些结点的边所构成，其准确定义下一小节给出图可以为日常很多应用建模，比如，交通和通信网，项目调度，博弈最基本的图算法包括：图遍历算法（如何遍历网络中所有结点），最小生成树算法（如何铺设最经济的通信网络），最短路径算法（如何确定两城市间的最佳路线），有向图的拓扑排序（如何确定专业课程的学习顺序），等等有些图论问题非常复杂，以至于最快的计算机也只能解决较小规。