《中科院计算机与信息学院 算法课 讲义》由会员分享，可在线阅读，更多相关《中科院计算机与信息学院 算法课 讲义（208页珍藏版）》请在金锄头文库上搜索。
1、 计算机算法设计与分析计算机算法设计与分析 讲讲 义义 2009 年年 8 月月 15 日日 北北 京京 目目 录录 第一章 复杂性分析初步 1 第一节 空间复杂性 1 第二节 时间复杂性 5 第三节 渐进符号 11 习题 一 15 第二章 图与遍历算法 18 第一节 图的基本概念和术语 18 第二节 图的遍历算法 25 第三节 双连通与网络可靠性 32 第四节 对策树 37 习题 二 42 附页 43 第三章 分治算法 45 第一节 算法的基本思想 45 第二节 排序算法 50 第三节 选择问题 58 第四节 关于矩阵乘法 61 第五节 最接近点对问题 63 习题 三 66 附页 72 第四
2、章 贪心算法 78 第一节 算法的基本思想 78 第二节 作业排序问题 82 第三节 最优生成树问题 87 第四节 单点源最短路径问题 90 第五节 Huffman 编码 93 习题 四 96 附页 98 第五章 动态规划算法 100 第一节 算法的基本思想 100 第二节 多段图问题 107 第三节 0/1 背包问题 109 第四节 流水作业调度问题 116 第五节 最有二叉搜索树 120 习题 五 124 第六章 回溯算法 126 第一节 算法的基本思想 126 第二节 定和子集问题与 0/1 背包问题 129 第三节 n-皇后问题与旅行商问题 135 第四节 图的着色问题 138 第五节
3、 回溯法的效率分析 140 附页 147 第七章 分枝限界算法 154 第一节 算法的基本思想 154 第二节 0/1 背包问题的分枝限界算法 156 第三节 电路板布线问题 160 第四节 LC检索 163 习题 七 169 附页 170 第八章 NP完全问题 175 第一节 算法基本思想 175 第二节 图灵机与确定性算法 179 第三节 NP 类问题 181 第四节 NP完全问题 188 第五节 证明新问题是 NP-完全问题的方法 191 第六节 NP困难问题 201 习题 八 203 1 第一章第一章 复杂性分析初步复杂性分析初步 程序性能（program performance）是指
4、运行一个程序所需的内存大小和时 间多少。所以，程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主 要包含两方面，即性能分析（performance analysis）与性能测量（performance measurement） ，前者采用分析的方法，后者采用实验的方法。 考虑空间复杂性的理由 考虑空间复杂性的理由 ? 在多用户系统中运行时，需指明分配给该程序的内存大小； ? 想预先知道计算机系统是否有足够的内存来运行该程序； ? 一个问题可能有若干个不同的内存需求解决方案，从中择取； ? 用空间复杂性来估计一个程序可能解决的问题的最大规模。 考虑时间复杂性的理由 考虑时间复杂性的理由 ?
5、 某些计算机用户需要提供程序运行时间的上限（用户可接受的） ； ? 所开发的程序需要提供一个满意的实时反应。 选取方案的规则：如果对于解决一个问题有多种可选的方案，那么方案的选 取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂性，最好 采取加权的方式进行评价。但是随着计算机技术的迅速发展，对空间的要求往往 不如对时间的要求那样强烈。因此我们这里的分析主要强调时间复杂性的分析。 1 空间复杂性 1 空间复杂性 ? 程序所需的空间程序所需的空间主要包括：指令空间、数据空间、环境栈空间。 指令空间指令空间用来存储经过编译之后的程序指令。大小取决于如下因素： ? 把程序编译成机器代码的编
6、译器； ? 编译时实际采用的编译器选项； ? 目标计算机。 注：所使用的编译器不同，则产生的机器代码的长度就会有差异；有些编译 器带有选项，如优化模式、覆盖模式等等。所取的选项不同，产生机器代码也会 不同。采用优化模式要多消耗时间。此外，目标计算机的配置也会影响代码的规 模。例如，如果计算机具有浮点处理硬件，那么，每个浮点操作可以转化为一条 机器指令。否则，必须生成仿真的浮点计算代码，使整个机器代码加长。一般情 况下，指令空间对于所解决的特定问题不够敏感。 数据空间数据空间用来存储所有常量和变量的值。 ? 存储常量和简单变量；所需的空间取决于所使用的计算机和编译器,以及 变量与常量的数目； 2
7、 ? 存储复合变量；包括数据结构所需的空间及动态分配的空间； ? 计算方法： 结构变量所占空间等于各个成员所占空间的累加； 数组变量所占空间等于 数组大小乘以单个数组元素所占的空间。例如 double a100; 所需空间为 1008800 int matrixrc; 所需空间为 4rc C+基本数据类型（32 位字长机器） C+基本数据类型（32 位字长机器） 类型名 说明 字节数范围 char 字符型 1 -128127 signed char 有符号字符型 1 -128127 unsigned char 无符号字符型 1 0255 shortint 短整型 2 -3276832767 s
8、igned shortint 有符号短整型 2 -3276832767 unsigned shortint 无符号短整型 2 065535 int 整型 4 -21474836482147483647 Signedint 有符号整型 4 -21474836482147483647 unsignedint 无符号整型 4 04294967295 longint 长整型 4 -21474836482147483647 signed longint 有符号长整型 4 -21474836482147483647 unsigned longint 无符号长整型 4 04294967295 float 单
9、精度浮点型 4 约 6 位有效数字 double 双精度浮点型 8 约 12 位有效数字 long double 长双精度浮点型16 约 15 位有效数字 环境栈空间环境栈空间保存函数调用返回时恢复运行所需要的信息。当一个函数被调 用时，下面数据将被保存在环境栈中： ? 返回地址； ? 所有局部变量的值、递归函数的传值形式参数的值； ? 所有引用参数以及常量引用参数的定义（此部分参看附录 1） 。 ? 实例特征实例特征: 决定问题规模的那些因素，主要指输入和输出的数量或相关数的 大小。如 对 n 个元素进行排序、nn 矩阵的加法等， n 作为实例特征；两 个 mn 矩阵的加法，以 n 和 m
10、两个数作为实例特征。 注注：指令空间的大小对于所解决的待定问题不够敏感。常量及简单变量所需 要的数据空间也独立于所解决的问题， 除非相关数的大小对于所选定的数据类型 3 来说实在太大。这时，要么改变数据类型要么使用多精度算法重写该程序，然后 再对新程序进行分析。 定长复合变量和未使用递归函数所需要的环境栈空间都独 立于问题的规模。 递归函数所需要的栈空间主要依赖于局部变量及形式参数所需 要的空间。除此外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次） 。 ? 程序所需要的空间可分为两部分： S(P) = c + SP(实例特征) 固定部分 c固定部分 c，它独立于实例的特征。主要包括指令
11、空间、简单变量、常量以 及定长复合变量所占用的空间； 可变部分S可变部分SP P， 主要包括复合变量所需的空间 （其大小依赖于所解决的具体问 题） 、动态分配的空间（依赖于实例的特征） 、递归栈所需的空间（依赖于 实例特征） 。 注注：一个精确的分析还应当包括编译期间所产生的临时变量所需的空间，这 种空间与编译器直接相关联，在递归程序中除了依赖于递归函数外，还依赖于实 例特征。但是，在考虑空间复杂性时，一般都被忽略。 程序 1-1-1 利用引用参数 template T Abc(T 在程序 1-1-1 中，采用T作为实 例特征。由于a，b，c都是引用 参数， 在函数中不需要为它们的 值分配空间
12、， 但需保存指向这些 参数的指针。若每个指针需要 2 个字节， 则共需要 6 字节的指针 空间。 此时函数所需要的总空间 是一个常量，而SAbc(实例特征) 0。 若函数Abc的参数是传值参数，则每个参数需要分配sizeof(T)的空间，于是 a， b， c所需的空间为 3sizeof(T)。 函数Abc所需的其他空间都与T无关， 故SAbc(实 例特征)3sizeof(T)。 如果假定使用a，b，c的大小作为实例特征，由于在传值参数的情形下，分 配给每个变量a，b，c的空间均为sizeof(T)，而不考虑这些变量中的实际值是多 大，所以，不论使用引用参数还是使用传值参数，都有SAbc(实例特征)0。 程序 1-1-2 顺序搜索 template int SequentialSearch(T a, const T for (i=0; i templ
