第一章引言 凡是学习了一种语言(不论是初级的还是高级的)程序设计课程并能编写 些实用程序的人,也许都有这样一种体会,学会编程容易,但是要想编出好程序 难,因而很想学点如何设计良好算法的知识。一些著名的计算机学家在有关计算 机科学教育的论述中认为,计算机科学是一种创造性思维活动,其教育必须面向 设计。计算机算法设计与分析正是面向设计、处于核心地位的课程。本课程本着 理论联系实际、以实际问题为背景、学以致用的原则,向大家讲解计算机算法设 计和性能分析的基本方法。 虽然人们对算法( algorithm)一词非常熟悉,可到目前为止,对于算法尚没 有统一而精确的定义。有人说:算法就是一组有穷的规则,它们规定了解决某 特定类型问题的一系列运算(《计算机算法基础》邹海明、余祥宣编)。而 Thomas H. Cormen等人在“ Introduction to Algorithms”一书中将算法描述为:算法是任 何定义好了的计算程式,它某些信或值的集合作为勃入,并产生某些值或 的橥合作为輸出。因此,算法是将输入转化为输出的一系列计算步骤。我们也可 以把算法看作解特定的计算问题的工具。概括起来,算法有以下五个特性: 1.确定性:算法的每一种运算(包括判断)必须要有确切的定义,即 每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 2.可实现性:此性质是指算法中有待实现的运算都是相当基本的,每 种运算至少在原理上能由人用纸和笔在有限的时间内完成。 3.具有数据输入:一个算法有零个或多个数据输入,它们是在算法开 始之前对算法最初赋予的量,这些输入取自特定的对象集合 4.具有数据输出:一个算法产生一个或多个输出,它们是同输入有某 种特定关系的量。 5.有穷性:一个算法总是在执行了有穷步之后终止 程序是算法的计算机高级语言描述,算法更可看成是程序的灵魂。一般来说, 拟定一个算法要经过设计、确认、分析、编码、检査、调试、计时等阶段。据此, 算法的学习大致可以分为五个方面 如何设计算法 如何表示算法 如何确认算法 如何分析算法 如何测试算法
第一章 引 言 凡是学习了一种语言（不论是初级的还是高级的）程序设计课程并能编写一 些实用程序的人，也许都有这样一种体会，学会编程容易，但是要想编出好程序 难，因而很想学点如何设计良好算法的知识。一些著名的计算机学家在有关计算 机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向 设计。计算机算法设计与分析正是面向设计、处于核心地位的课程。本课程本着 理论联系实际、以实际问题为背景、学以致用的原则，向大家讲解计算机算法设 计和性能分析的基本方法。 虽然人们对算法（algorithm）一词非常熟悉，可到目前为止，对于算法尚没 有统一而精确的定义。有人说：算法就是一组有穷的规则，它们规定了解决某一 特定类型问题的一系列运算（《计算机算法基础》邹海明、余祥宣编）。而 Thomas H. Cormen 等人在“Introduction to Algorithms”一书中将算法描述为：算法是任 何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值 的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。我们也可 以把算法看作解特定的计算问题的工具。概括起来，算法有以下五个特性： 1． 确定性： 算法的每一种运算（包括判断）必须要有确切的定义，即 每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 2． 可实现性： 此性质是指算法中有待实现的运算都是相当基本的，每 种运算至少在原理上能由人用纸和笔在有限的时间内完成。 3． 具有数据输入： 一个算法有零个或多个数据输入，它们是在算法开 始之前对算法最初赋予的量，这些输入取自特定的对象集合。 4． 具有数据输出： 一个算法产生一个或多个输出，它们是同输入有某 种特定关系的量。 5． 有穷性： 一个算法总是在执行了有穷步之后终止。 程序是算法的计算机高级语言描述，算法更可看成是程序的灵魂。一般来说， 拟定一个算法要经过设计、确认、分析、编码、检查、调试、计时等阶段。据此， 算法的学习大致可以分为五个方面： ¾ 如何设计算法 ¾ 如何表示算法 ¾ 如何确认算法 ¾ 如何分析算法 ¾ 如何测试算法
教学大纲 课程编号 课程属性|学科基础课|学时/学分 中文课程名称计算机算法设计与分析 英文课程名称| The Design and Analysis of Computer Algorithms 预备知识离散数学、数据结构、高级程序设计语言C、C++ 教学目的计算机及相关学科硕士研究生的基础课。使学生掌握计算机 和要求算法的通用设计方法,学会分析算法的空间和时间复杂性 第一章引言:介绍算法概念及相关领域、算法的时间和空 间复杂性分析基础知识 第二章基本搜索和遍历技术:介绍二叉树、树及图的遍历 和搜索技术,BFS算法及其复杂性分析 第三章分治算法:算法的基本思想、归并排序、快速排序、 最短路经、选择问题等实例分析。 第四章贪心算法:最优化问题、贪心算法的基本思想、背 主要内容 包问题、旅行商问题、最短路径问题等实例分析。 重点、难点第五章动态规划方法:问题背景、01背包问题、矩阵乘法 链、旅行商问题等。 第六章回溯法:算法基本思想、装箱问题、背包问题、旅 行商问题、电路板排列问题等实例分析。 第七章分支定界法:算法思想、装箱问题、O/1背包问题 旅行商问题、电路板排列等实例分析。 第八章NP一难度问题和NP一完全问题简介,证明NP完 全性的方法介绍。 发展方向|计算机算法设计和软件开发 考核办法‖平时考察20%+期末闭卷考试80% 1.余祥宣等,《计算机算法基础》,华中理工大学出版社,2000。 参考资料2.(美) Cormen,TH等,《算法导论》,高等教育出版社,2001 3.王晓东,《计算机算法设计与分析》,电子工业出版社,2001。 撰写人 陈玉福 撰写日 2002年7月25日
教 学 大 纲 课程编号 课程属性 学科基础课 学时/学分 中文课程名称 计算机算法设计与分析 英文课程名称 The Design and Analysis of Computer Algorithms 预 备 知 识 离散数学、数据结构、高级程序设计语言 C、C＋＋ 教 学 目 的 和 要 求 计算机及相关学科硕士研究生的基础课。使学生掌握计算机 算法的通用设计方法，学会分析算法的空间和时间复杂性。 第一章 引言： 介绍算法概念及相关领域、算法的时间和空 间复杂性分析基础知识。 第二章 基本搜索和遍历技术：介绍二叉树、树及图的遍历 和搜索技术，BFS 算法及其复杂性分析。 第三章 分治算法：算法的基本思想、归并排序、快速排序、 最短路经、选择问题等实例分析。 第四章 贪心算法：最优化问题、贪心算法的基本思想、背 包问题、旅行商问题、最短路径问题等实例分析。 第五章 动态规划方法：问题背景、0/1 背包问题、矩阵乘法 链、旅行商问题等。 第六章 回溯法：算法基本思想、装箱问题、背包问题、旅 行商问题、电路板排列问题等实例分析。 第七章 分支定界法：算法思想、装箱问题、0/1 背包问题、 旅行商问题、电路板排列等实例分析。 主 要 内 容、 重点、难点 第八章 NP－难度问题和 NP－完全问题简介，证明 NP 完 全性的方法介绍。 发 展 方 向 计算机算法设计和软件开发 考 核 办 法 平时考察 20％＋期末闭卷考试 80％ 参 考 资 料 1． 余祥宣等，《计算机算法基础》，华中理工大学出版社，2000。 2．（美）Cormen，T.H. 等，《算法导论》，高等教育出版社，2001。 3． 王晓东，《计算机算法设计与分析》，电子工业出版社，2001。 撰 写 人 陈 玉 福 撰 写 日 期 2002 年 7 月 25 日
第二章复杂性分析初步 程序性能( program performance)是指运行一个程序所需的内存大小和时 间多少。所以,程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主 要包含两方面,即性能分析( performance analysis)与性能测量( performance measurement),前者采用分析的方法,后者采用实验的方法。 考虑空间复杂性的理由 在多用户系统中运行时,需指明分配给该程序的内存大小 想预先知道计算机系统是否有足够的内存来运行该程序 个问题可能有若干个不同的内存需求解决方案,从中择取; 用空间复杂性来估计一个程序可能解决的问题的最大规模。 考虑时间复杂性的理由 某些计算机用户需要提供程序运行时间的上限(用户可接受的); 所开发的程序需要提供一个满意的实时反应。 选取方案的规则:如果对于解决一个问题有多种可选的方案,那么方案的 选取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂 性,最好采取加权的方式进行评价。但是随着计算机技术的迅速发展,对 空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强 调时间复杂性的分析 §1空间复杂性 程序所需要的空间: ●指令空间一用来存储经过编译之后的程序指令。程序所需的指令空间的大小 取决于如下因素: 把程序编译成机器代码的编译器 编译时实际采用的编译器选项; 目标计算机 所使用的编译器不同,则产生的机器代码的长度就会有差异;有些编译器带 有选项,如优化模式、覆盖模式等等。所取的选项不同,产生机器代码也会不同 此外,目标计算机的配置也会影响代码的规模。例如,如果计算机具有浮点处理 硬件,那么,每个浮点操作可以转化为一条机器指令。否则,必须生成仿真的浮 点计算代码,使整个机器代码加长。一般情况下,指令空间对于所解决的特定间 题不够敏感。 数据空间一用来存储所有常量和变量的值。分成两部分:a).存储常量和简 单变量;b).存储复合变量。前者所需的空间取决于所使用的计算机和编译
第二章 复杂性分析初步 程序性能（program performance）是指运行一个程序所需的内存大小和时 间多少。所以，程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主 要包含两方面，即性能分析（performance analysis）与性能测量（performance measurement），前者采用分析的方法，后者采用实验的方法。 考虑空间复杂性的理由 9 在多用户系统中运行时，需指明分配给该程序的内存大小； 9 想预先知道计算机系统是否有足够的内存来运行该程序； 9 一个问题可能有若干个不同的内存需求解决方案，从中择取； 9 用空间复杂性来估计一个程序可能解决的问题的最大规模。 考虑时间复杂性的理由 9 某些计算机用户需要提供程序运行时间的上限（用户可接受的）； 9 所开发的程序需要提供一个满意的实时反应。 选取方案的规则：如果对于解决一个问题有多种可选的方案，那么方案的 选取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂 性，最好采取加权的方式进行评价。但是随着计算机技术的迅速发展，对 空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强 调时间复杂性的分析。 §1 空间复杂性 程序所需要的空间： z 指令空间－用来存储经过编译之后的程序指令。程序所需的指令空间的大小 取决于如下因素： 9 把程序编译成机器代码的编译器； 9 编译时实际采用的编译器选项； 9 目标计算机。 所使用的编译器不同，则产生的机器代码的长度就会有差异；有些编译器带 有选项，如优化模式、覆盖模式等等。所取的选项不同，产生机器代码也会不同。 此外，目标计算机的配置也会影响代码的规模。例如，如果计算机具有浮点处理 硬件，那么，每个浮点操作可以转化为一条机器指令。否则，必须生成仿真的浮 点计算代码，使整个机器代码加长。一般情况下，指令空间对于所解决的特定问 题不够敏感。 z 数据空间－用来存储所有常量和变量的值。分成两部分：a).存储常量和简 单变量；b).存储复合变量。前者所需的空间取决于所使用的计算机和编译
器,以及变量与常量的数目,这是由于我们往往是计算所需内存的字节数, 而每个字节所占的数位依赖于具体的机器环境。后者包括数据结构所需的空 间及动态分配的空间 占用字节数 适用范围 char -128127 unsigned char 0~255 short In unsigned int on unsigned long 112224448 3276832767 3276832767 0~23-1 float ±3.4E±38 double 士1.7E±308 long double 3.4E-49321.1E+4932 inter (near,cs,ds,es,ss指针) inter 4 (far,huge指针) 在16位计算机上, Borland c++中各种变量所占空间 计算方法:结构变量所占空间等于各个成员所占空间的累加;数组变量所占 空间等于数组大小乘以单个数组元素所占的空间。例如 double a[10];所需空间为100×8=800 int matrix[r][c];所需空间为2×r× ●环境栈空间一保存函数调用还回时恢复运行所需要的信息。当一个函数被调 用时,下面数据将被保存在环境栈中 √返回地址 所有局部变量的值、递归函数的传值形式参数的值; 所有引用参数以及常量引用参数的定义。 在分析空间复杂性中,实例特征的概念非常重要。所谓实例特征是指决定问 题规模的那些因素。如,输入和输出的数量或相关数的大小,如对n个元素进行 排序、n×n矩阵的加法等,都可以n作为实例特征,而两个mXn矩阵的加法应 该以n和m两个数作为实例特征 指令空间的大小对于所解决的待定问题不够敏感。常量及简单变量所需要的 数数据空间也独立于所解决的问题,除非相关数的大小对于所选定的数据类型来 说实在太大。这时,要么改变数据类型要么使用多精度算法重写该程序,然后再
器,以及变量与常量的数目，这是由于我们往往是计算所需内存的字节数， 而每个字节所占的数位依赖于具体的机器环境。后者包括数据结构所需的空 间及动态分配的空间。 z 类型 占用字节数 适用范围 char 1 -128~127 unsigned char 1 0~255 short 2 -32768~32 767 int 2 -32768~32 767 unsigned int 2 0~65 535 long 4 -2 31～2 31-1 unsigned long 4 0~2 31-1 float 4 ±3.4E ±38 double 8 ±1.7E ±308 long double 10 3.4E -4932~1.1E +4932 pointer 2 (near,_cs,_ds,_es,_ss 指针) pointer 4 (far, huge 指针) 在 16 位计算机上，Borland C++中各种变量所占空间 计算方法：结构变量所占空间等于各个成员所占空间的累加；数组变量所占 空间等于数组大小乘以单个数组元素所占的空间。例如 double a[100]; 所需空间为 100×8＝800 int matrix[r][c]; 所需空间为 2×r×c z 环境栈空间－保存函数调用还回时恢复运行所需要的信息。当一个函数被调 用时，下面数据将被保存在环境栈中： 9 返回地址； 9 所有局部变量的值、递归函数的传值形式参数的值； 9 所有引用参数以及常量引用参数的定义。 在分析空间复杂性中，实例特征的概念非常重要。所谓实例特征是指决定问 题规模的那些因素。如，输入和输出的数量或相关数的大小，如对 n 个元素进行 排序、n×n 矩阵的加法等，都可以 n 作为实例特征，而两个 m×n 矩阵的加法应 该以 n 和 m 两个数作为实例特征。 指令空间的大小对于所解决的待定问题不够敏感。常量及简单变量所需要的 数数据空间也独立于所解决的问题，除非相关数的大小对于所选定的数据类型来 说实在太大。这时，要么改变数据类型要么使用多精度算法重写该程序，然后再
对新程序进行分析。 复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独 立于实例的特征,除非正在使用递归函数。在使用递归函数时,实例特征通常会 影响环境栈所需要的空间数量。 递归函数所需要的栈空间主要依赖于局部变量及形式参数所需要的空间。除 此外,该空间还依赖于递归的深度(即嵌套递归调用的最大层次) 综合以上分析,一个程序所需要的空间可分为两部分: 固定部分,它独立于实例的特征。主要包括指令空间、简单变量以及定 长复合变量所占用的空间、常量所占用的空; 可变部分,主要包括复合变量所需的空间(其大小依赖于所解决的具体 问题)、动态分配的空间(依赖于实例的特征)、递归栈所需的空间(依赖于实例 特征) 令S(P)表示程序P需要的空间,则有 S(P)=c+Sp(实例特征) 其中c表示固定部分所需要的空间,是一个常数;S表示可变部分所需要的空 间。在分析程序的空间复杂性时,一般着重于估算Sp(实例特征)。实例特征的选 择一般受到相关数的数量以及程序输入和输出规模的制约 注:一个精确的分析还应当包括编译期间所产生的临时变量所需的空间,这 种空间与编译器直接相关联,在递归程序中除了依赖于递归函数外,还依赖于实 例特征。但是,在考虑空间复杂性时,一般都被忽略。 例子 程序2-1-1利用引用参数 在程序2-1-1中,采用T作为实例特征。由 template class t> 于a,b,c都是引用参数,在函数中不需要 T Abc (t& a, t& b, T& c) 为它们的值分配空间,但需保存指向这些参 数的指针。若每个指针需要2个字节,则共 需要6字节的指针空间。此时函数所需要的 return a+b+c+b*c\ 总空间是一个常量,而Sme(实例特征)=0。 +(a+b+c)/(a+b)+4 但若函数Abc的参数是传值参数,则每个参 数需要分配 sizeof(T)的空间,于是a,b c所需的空间为3× sizeof(T)。函数Abc所 需要的其他空间都与T无关,故S(实例特征)=3× sizeof(T)。 如果假定使用a,b,c的大小作为实例特征,由于在传值参数的情形下, 分配给每个变量a,b,c的空间均为 sizeof(T),而不考虑这些变量中的实际值
对新程序进行分析。 复合变量及动态分配所需要的空间同样独立于问题的规模。而环境栈通常独 立于实例的特征，除非正在使用递归函数。在使用递归函数时，实例特征通常会 影响环境栈所需要的空间数量。 递归函数所需要的栈空间主要依赖于局部变量及形式参数所需要的空间。除 此外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次）。 综合以上分析，一个程序所需要的空间可分为两部分： ¾ 固定部分，它独立于实例的特征。主要包括指令空间、简单变量以及定 长复合变量所占用的空间、常量所占用的空； ¾ 可变部分，主要包括复合变量所需的空间（其大小依赖于所解决的具体 问题）、动态分配的空间（依赖于实例的特征）、递归栈所需的空间（依赖于实例 特征）。 令 S(P)表示程序 P 需要的空间，则有 S(P) = c + SP(实例特征) 其中 c 表示固定部分所需要的空间，是一个常数；SP 表示可变部分所需要的空 间。在分析程序的空间复杂性时，一般着重于估算 SP(实例特征)。实例特征的选 择一般受到相关数的数量以及程序输入和输出规模的制约。 注：一个精确的分析还应当包括编译期间所产生的临时变量所需的空间，这 种空间与编译器直接相关联，在递归程序中除了依赖于递归函数外，还依赖于实 例特征。但是，在考虑空间复杂性时，一般都被忽略。 例子 程序 2-1-1 利用引用参数 template T Abc(T& a, T& b, T& c) { return a+b+c+b*c\ +(a+b+c)/(a+b)+4; } 需要的其他空间都与 T 无关，故 SAbc(实例特征)＝3×sizeof(T)。 如果假定使用 a，b，c 的大小作为实例特征，由于在传值参数的情形下， 分配给每个变量 a，b，c 的空间均为 sizeof(T)，而不考虑这些变量中的实际值 在程序 2-1-1 中，采用 T 作为实例特征。由 于 a，b，c 都是引用参数，在函数中不需要 为它们的值分配空间，但需保存指向这些参 数的指针。若每个指针需要 2 个字节，则共 需要 6 字节的指针空间。此时函数所需要的 总空间是一个常量，而 SAbc(实例特征)＝0。 但若函数 Abc 的参数是传值参数，则每个参 数需要分配 sizeof(T)的空间，于是 a，b， c 所需的空间为 3×sizeof(T)。函数 Abc 所
是多大,所以,不论使用引用参数还是使用传值参数,都有SA(实例特征)=0 程序2-1-2顺序搜索 template int SequentialSearch (T al,\ const T& x, int n /在a[0:n-1]中搜索x,若找到则//回所在的位置,否则返回-1 int 1 for(i=0: i template T Sum ( t a, int n) T Rsum(t a[, int n) U/计算a[0:n1]的和 /计算a[0:n-1]的和 t tsum=0: if (n>0) for(int i=0: i<n: i++) return Rsum(a, n-1)+a[n-1] sumt=a return return tsum:
是多大，所以，不论使用引用参数还是使用传值参数，都有 SAbc(实例特征)＝0。 程序 2-1-2 顺序搜索 template int SequentialSearch(T a[],\ const T& x, int n) {//在 a[0:n-1]中搜索 x,若找到则//回所在的位置，否则返回-1 int i; for (i=0; i template T Sum(T a[], int n) T Rsum(T a[], int n) {//计算 a[0:n-1]的和 {//计算 a[0:n-1]的和 T tsum=0； if (n>0) for (int i=0; i<n; i++) return Rsum(a,n-1)+a[n-1]; tsum+=a[i]; return 0; return tsum; } }
嵌套调用一直进行到n=0。可见,递归计算比累加计算需要更多的空间。 Rsum(a, n) Rsum(a, n-1) Rsum(a, 1) §2时间复杂性 时间复杂性的构成 个程序所占时间T(P)=编辑时间+运行时间 编译时间与实例特征无关,而且,一般情况下,一个编译过的程序可以 运行若干次,所以,人们主要关注的是运行时间,记做tp(实例特征) 如果了解所用编辑器的特征,就可以确定代码P进行加、减、乘、除、 比较、读、写等所需的时间,从而得到计算tp的公式。令n代表实例特 征(这里主要是问题的规模),则有如下的表示式 t(n)=c.add(n)+Cs SUB (n)+c MUL (n)+c DIV (n)+c CMP (n)+ 其中,ca,c3,cn,ca,c分别表示一次加、减、乘、除及比较操作所需的时间, 函数ADD,SUB,ML,DIV,CMP分别表示代码P中所使用的加、减、乘、除及比 较操作的次数 个算术操作所需的时间取决于操作数的类型(int、 float、 double 等等),所以,有必要对操作按照数据类型进行分类: 在构思一个程序时,影响tp的许多因素还是未知的,所以,在多数情 况下仅仅是对tp进行估计。 估算运行时间的方法:A.找一个或多个关键操作,确定这些关键操作 所需要的执行时间(对于前面所列举的四种算术运算及比较操作,一般 被看作是基本操作,并约定所用的时间都是一个单位);B.确定程序总 的执行步数 操作计数 首先选择一种或多种操作(如加、乘和比较等),然后计算这些操作分别执 行了多少次。关键操作对时间复杂性影响最大
嵌套调用一直进行到 n＝0。可见，递归计算比累加计算需要更多的空间。 上述递归程序的嵌套调用层次 §2 时间复杂性 z 时间复杂性的构成 9 一个程序所占时间 T(P)=编辑时间+运行时间； 9 编译时间与实例特征无关，而且，一般情况下，一个编译过的程序可以 运行若干次，所以，人们主要关注的是运行时间，记做 tP(实例特征)； 9 如果了解所用编辑器的特征，就可以确定代码 P 进行加、减、乘、除、 比较、读、写等所需的时间，从而得到计算 tP的公式。令 n 代表实例特 征（这里主要是问题的规模），则有如下的表示式： tP(n)=caADD(n)+csSUB(n)+cmMUL(n)+cdDIV(n)+ccCMP(n)+··· 其中，ca，cs，cm，cd，cc分别表示一次加、减、乘、除及比较操作所需的时间， 函数 ADD，SUB，MUL，DIV，CMP 分别表示代码 P 中所使用的加、减、乘、除及比 较操作的次数； 9 一个算术操作所需的时间取决于操作数的类型（int、float、double 等等），所以，有必要对操作按照数据类型进行分类； 9 在构思一个程序时，影响 tP 的许多因素还是未知的，所以，在多数情 况下仅仅是对 tP进行估计。 9 估算运行时间的方法：A. 找一个或多个关键操作，确定这些关键操作 所需要的执行时间（对于前面所列举的四种算术运算及比较操作，一般 被看作是基本操作，并约定所用的时间都是一个单位）；B. 确定程序总 的执行步数。 z 操作计数 首先选择一种或多种操作（如加、乘和比较等），然后计算这些操作分别执 行了多少次。关键操作对时间复杂性影响最大。 Rsum(a, n) Rsum(a, n-1) . . . Rsum(a, 1) Rsum(a, 0)
程序2-2-1寻找最大元素 template int Max(t a[, int n) /寻找a[0:n-1]中的最大元素 int pos=0 for (int i=l: i T Horner(t coeff[, int n, const T& x)
程序 2-2-1 寻找最大元素 template int Max(T a[], int n) {//寻找 a[0:n-1]中的最大元素 int pos=0; for (int i=1; i T PolyEval(T coeff[], int n, const T& x) {//计算 n 次多项式的值，coeff[0:n]为多项式的系数 T y=1, value=coeff[0]; for (int i=1; i T Horner(T coeff[], int n, const T& x)
//计算n次多项式的值, coeff[0:n为多项式的系数 T value=coeff[n for(i=l: i-n: i+ //n循环 T value= value*x+ coeff[n-i];//一次加法和一次乘法 return value //2n次基本运算 这里,关键操作是加法与乘法运算。在程序2-2-2中,for循环的每一回都 执行两次乘法运算和一次加法运算。所以程序的总的运算次数为3n。在程序 2-2-3中,for循环的每一回都执行乘法与加法运算各一次,程序总的运算次数 为2n。再考察下面两例: 程序2-2-4计算名次 程序2-2-5选择排序 templateclass T> templateclass t> oid Rank(t al, int n, int rl void Selectionsort (T a[, int n) U/计算a[0:n1]中元素的排名 /对数组a[0:n-1]中元素排序 for (int i=l: i1: size- r[i]=0;/初始化 int j=Max(a, size //逐对比较所有的元素 Swap(alj], alsize-l]) for (int i=l: i 比较。在2-2-4中,对于每个i inline void Swap(T& a. T& b) 的取值,执行比较的次数是i /交换a和b 总的比较次数为1+2+…+n-1 T temp=a; a=b; b= temp =(n-1)n/2。在此,for循环的 额外开销、初始化数组r的开 销、以及每次比较a中两个素时对r进行的增值开销都未列入其中。在程序2-2-5 给出的排序中,首先找出最大元素,把它移动到a[n-1],然后在余下的n-1个 元素中再寻找最大的元素,并把它移动到a[n-2].如此进行下去,此种方法称为 选择排序( selection sort).从程序2-2-1中已经知道,每次调用Max(a,size)
{//计算 n 次多项式的值，coeff[0:n]为多项式的系数 T value=coeff[n]; for(i=1; i template void Rank(T a[], int n, int r[]) void Selectionsort(T a[], int n) {//计算 a[0:n-1]中元素的排名 {//对数组 a[0:n-1]中元素排序 for(int i=1; i1; size--) r[i]=0; //初始化 { int j=Max(a,size); //逐对比较所有的元素 Swap(a[j],a[size-1]); for(int i=1; i inline void Swap(T& a. T& b) {//交换 a 和 b T temp=a; a=b; b=temp; }
需要执行size-1次比较,所以总的比较次数为1+2+ 每调用一次函数Swap需要执行三次元素移动,所需要总的移动次数为3(n-1) 当然,在本程序运行中同样会有其它开销,在此未予考虑。 考虑冒泡排序( bubble sort)。冒泡排序是从左向右逐个检查,对相邻的 元素进行比较,若左边的元素比右边的元素大,则交换这两个元素。如数组 5,3,7,4,11,2]:比较5和3,交换;比较5和7,不交换;比较7和4,交换; 比较7和11,不交换;比较11和2,交换。这个行程称为一次冒泡,经一次冒 泡后,原数组变为[3,5,4,7,2,1].可见,数组中最大的数被移动到最右的位置 下一次冒泡只对数组[3,5,4,7,2]进行即可。如此进行下去,最后将原数组按递 增的顺序排列 程序2-7一次冒泡 程序2-2-8冒泡排序 templateclass t> Template void Bubble (t al, int n)void Bubble Sort(t al, int n) for (int i=0; i1; I-) if(ali]>a[i+1]) Swap(ali], a[i+1]) Bubble(a, D) 在程序2-3-7中,for循环的每一回都执行了一次比较和三次元素的移动, 因而总的操作数为4n。在程序2-3-8中,对于每个i,调用函数 Bubble(a,i)需 要执行4i次操作,因而总的操作数为2n(n-1).这里我们照例忽略了非主要操作, 分析程序2-3-7发现,在问题实例中,如果数组本身是递增的,则每一次 冒泡都不需要交换数据,而如果薮组是严格递减的,则第一次冒泡要交换数据 n-1次。这里我们都取数组元素个数为实例特征,但操作数却是不同的。因而, 人们往往还会关心最好的、最坏的和平均的操作数是多少。令P表示一个程序, 将操作计数O(n2n2,…n1)视为实例特征n1,n2…,n的函数。令 operation2(D)表示程序实例I的操作计数,S(n1,n2,…,n2)为所讨论程序的 具有实例特征n12n2…,n的实例之集,则 P最好的操作计数为 O(n1n2…,n)=min{ operation2(D)|I∈S(n,n2…,n)} P最坏的操作计数为 O"(n1n2…,n,)=max{ operation(D)|I∈S(n,n2,…,n1)}
需要执行 size-1 次比较，所以总的比较次数为 1+2+ ··· + n-1=(n-1)n/2. 每调用一次函数 Swap 需要执行三次元素移动，所需要总的移动次数为 3(n-1). 当然，在本程序运行中同样会有其它开销，在此未予考虑。 考虑冒泡排序（bubble sort）。冒泡排序是从左向右逐个检查，对相邻的 元素进行比较，若左边的元素比右边的元素大，则交换这两个元素。如数组 [5,3,7,4,11,2]：比较 5 和 3，交换；比较 5 和 7，不交换；比较 7 和 4，交换； 比较 7 和 11，不交换；比较 11 和 2，交换。这个行程称为一次冒泡，经一次冒 泡后，原数组变为[3,5,4,7,2,11].可见，数组中最大的数被移动到最右的位置。 下一次冒泡只对数组[3,5,4,7,2]进行即可。如此进行下去，最后将原数组按递 增的顺序排列。 程序 2-2-7 一次冒泡 程序 2-2-8 冒泡排序 template void Bubble(T a[], int n)void { for(int i=0; ia[i+1]) Swap(a[i],a[i+1]); } 在程序 2-3-7 中，for 循环的每一回都执行了一次比较和三次元素的移动， 因而总的操作数为 4n。在程序 2-3-8 中，对于每个 i，调用函数 Bubble(a,i)需 要执行 4i 次操作，因而总的操作数为 2n(n-1).这里我们照例忽略了非主要操作。 分析程序 2-3-7 发现，在问题实例中，如果数组本身是递增的，则每一次 冒泡都不需要交换数据，而如果数组是严格递减的，则第一次冒泡要交换数据 n-1 次。这里我们都取数组元素个数为实例特征，但操作数却是不同的。因而， 人们往往还会关心最好的、最坏的和平均的操作数是多少。令 P 表示一个程序， 将操作计数 ( , , , ) P 1 2 k O n n L n 视为实例特征 k n , n , , n 1 2 L 的函数。令 operation (I) P 表示程序实例 I 的操作计数， ( , , , ) 1 2 k S n n L n 为所讨论程序的 具有实例特征 k n , n , , n 1 2 L 的实例之集，则 P 最好的操作计数为 ( , , ) min{ ( ) | ( , , , )} 1, 2 k P 1 2 k BC OP n n L n = operation I I ∈ S n n L n P 最坏的操作计数为 ( , , ) max{ ( ) | ( , , , )} 1, 2 k P 1 2 k WC OP n n L n = operation I I ∈ S n n L n Template BubbleSort(T a[], int n) { for(int I=n; I>1; I--) Bubble(a, I); }