第一章 引 言 凡是学习了一种语言（不论是初级的还是高级的）程序设计课程并能编写一 些实用程序的人，也许都有这样一种体会，学会编程容易，但是要想编出好程序 难，因而很想学点如何设计良好算法的知识。一些著名的计算机学家在有关计算 机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向 设计。计算机算法设计与分析正是面向设计、处于核心地位的课程。本课程本着 理论联系实际、以实际问题为背景、学以致用的原则，向大家讲解计算机算法设 计和性能分析的基本方法。 虽然人们对算法（ algorithm）一词非常熟悉，可到目前为止，对于算法尚没 有统一而精确的定义。有人说：算法就是一组有穷的规则，它们规定了解决某一 特定类型问题的一系列运算（ 《计算机算法基础》邹海明、余祥宣编） 。而 Thomas H. Cormen 等人在“ Introduction to Algorithms”一书中将算法描述为： 算法是任 何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值 的集合作为输出。 因此，算法是将输入转化为输出的一系列计算步骤。我们也可 以把算法看作解特定的计算问题的工具。概括起来，算法有以下五个特性： 1． 确定性： 算法的每一种运算（包括判断）必须要有确切的定义，即 每一种运算应该执行何种动作必须是相当清楚的、无二义性的。 2． 可实现性： 此性质是指算法中有待实现的运算都是相当基本的，每 种运算至少在原理上能由人用纸和笔在有限的时间内完成。 3． 具有数据输入： 一个算法有零个或多个数据输入，它们是在算法开 始之前对算法最初赋予的量，这些输入取自特定的对象集合。 4． 具有数据输出： 一个算法产生一个或多个输出，它们是同输入有某 种特定关系的量。 5． 有穷性： 一个算法总是在执行了有穷步之后终止。 程序是算法的计算机高级语言描述， 算法更可看成是程序的灵魂。 一般来说， 拟定一个算法要经过设计、确认、分析、编码、检查、调试、计时等阶段。据此， 算法的学习大致可以分为五个方面： null 如何设计算法 null 如何表示算法 null 如何确认算法 null 如何分析算法 null 如何测试算法 教 学 大 纲 课程编号 课程属性 学科基础课 学时 /学分 中文课程名称 计算机算法设计与分析 英文课程名称 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） ，前者采用分析的方法，后者采用实验的方法。 考虑空间复杂性的理由 null 在多用户系统中运行时，需指明分配给该程序的内存大小； null 想预先知道计算机系统是否有足够的内存来运行该程序； null 一个问题可能有若干个不同的内存需求解决方案，从中择取； null 用空间复杂性来估计一个程序可能解决的问题的最大规模。 考虑时间复杂性的理由 null 某些计算机用户需要提供程序运行时间的上限（用户可接受的） ； null 所开发的程序需要提供一个满意的实时反应。 选取方案的规则：如果对于解决一个 问题有多种可选的方案，那么方案的 选取要基于这些方案之间的性能差异 。对于各种方案的时间及空间的复杂 性，最好采取加权的方式进行评价。 但是随着计算机技术的迅速发展，对 空间的要求往往不如对时间的要求那 样强烈。因此我们这里的分析主要强 调时间复杂性的分析。 §1 空间复杂性 程序所需要的空间： null 指令空间 －用来存储经过编译之后的程序指令。程序所需的指令空间的大小 取决于如下因素： null 把程序编译成机器代码的编译器； null 编译时实际采用的编译器选项； null 目标计算机。 所使用的编译器不同，则产生的机器代码的长度就会有差异；有些编译器带 有选项，如优化模式、覆盖模式等等。所取的选项不同，产生机器代码也会不同。 此外，目标计算机的配置也会影响代码的规模。例如，如果计算机具有浮点处理 硬件，那么，每个浮点操作可以转化为一条机器指令。否则，必须生成仿真的浮 点计算代码，使整个机器代码加长。一般情况下，指令空间对于所解决的特定问 题不够敏感 。 null 数据空间 －用来存储所有常量和变量的值。分成两部分： a).存储常量和简 单变量；b).存储复合变量。前者所需的空间取决于所使用的计算机和编译 器,以及变量与常量的数目，这是由于我们往 往是计算所需内存的字节数， 而每个字节所占的数位依赖于具体的机器环境。后者包括数据结构所需的空 间及动态分配的空间。 null 类型 占用字节数 适用范围 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 null 环境栈空间 －保存函数调用还回时恢复运行所需要的信息。当一个函数被调 用时，下面数据将被保存在环境栈中： null 返回地址； null 所有局部变量的值、递归函数的传值形式参数的值； null 所有引用参数以及常量引用参数的定义。 在分析空间复杂性中，实例特征的概念非常重要。所谓实例特征是指决定问 题规模的那些因素。如，输入和输出的数量或相关数的大小，如对n个元素进行 排序、n×n矩阵的加法等，都可以n作为实例特征，而两个m×n矩阵的加法应 该以n和m 两个数作为实例特征。 指令空间的大小对于所解决的待定问题不够敏感。 常量及简单变量所需要的 数数据空间也独立于所解决的问题， 除非相关数的大小对于所选定的数据类型来 说实在太大。这时，要么改变数据类型要么使用多精度算法重写该程序，然后再 对新程序进行分析。 复合变量及动态分配所需要的空间同样独立于问题的规模。 而环境栈通常独 立于实例的特征，除非正在使用递归函数。在使用递归函数时，实例特征通常会 影响环境栈所需要的空间数量。 递归函数所需要的栈空间主要依赖于局部变量及形式参数所需要的空间。 除 此外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次） 。 综合以上分析， 一个程序所需要的空间可分为两部分： null 固定部分 ，它独立于实例的特征。主要包括指令空间、简单变量以及定 长复合变量所占用的空间、常量所占用的空； null 可变部分 ，主要包括复合变量所需的空间（其大小依赖于所解决的具体 问题） 、动态分配的空间（依赖于实例的特征） 、递归栈所需的空间（依赖于实例 特征） 。 令S(P)表示程序P需要的空间，则有 S(P) = c + S P (实例特征) 其中 c 表示固定部分所需要的空间，是一个常数；S P 表示可变部分所需要的空 间。在分析程序的空间复杂性时，一般着重于估算S P (实例特征)。实例特征的选 择一般受到相关数的数量以及程序输入和输出规模的制约。 注 ：一个精确的分析还应当包括编译期间所产生的临时变量所需的空间，这 种空间与编译器直接相关联，在递归程序中除了依赖于递归函数外，还依赖于实 例特征。但是，在考虑空间复杂性时，一般都被忽略。 例子 程序2-1-1 利用引用参数 template < class T > T Abc(T& a, T& b, T& c) { return a+b+c+b*c\ +(a+b+c)/(a+b)+4; } 需要的其他空间都与T无关，故S Abc (实例特征)＝3×sizeof(T)。 如果假定使用 a，b，c 的大小作为实例特征，由于在传值参数的情形下， 分配给每个变量a，b，c的空间均为sizeof(T)，而不考虑这些变量中的实际值 在程序2-1-1中，采用T作为实例特征。由 于a，b，c都是引用参数，在函数中不需要 为它们的值分配空间，但需保存指向这些参 数的指针。若每个指针需要2个字节，则共 需要 6 字节的指针空间。此时函数所需要的 总空间是一个常量，而S Abc (实例特征)＝0。 但若函数Abc的参数是传值参数，则每个参 数需要分配sizeof(T)的空间，于是a，b， c所需的空间为3×sizeof(T)。函数Abc所 是多大，所以，不论使用引用参数还是使用传值参数，都有S Abc (实例特征)＝0。 程序2-1-2 顺序搜索 template < class T > int SequentialSearch(T a[],\ const T& x, int n) {//在a[0:n-1]中搜索x,若找到则//回所在的位置，否则返回-1 int i; for (i=0; i<n && a[i]=!x; i++); if (i==n) return -1; return i; } 在程序 2-1 中，假定采用被查数组的长度 n 作为实例特征，并 取T为int 类型。数组中每个元素需要2个字节，实参 x需要2个字节，传值形式参数n 需 要 2 个字节，局部变量 i 需要 2 个字节，整数常量-1 需要 2 个字节，所需要的 总的数据空间为 10 个字节，其独立于 n，所以 S 顺序搜索 (n)＝0。这里，我们并未 把数组 a 所需要的空间计算进来，因为该数组所需要的空间已在定义实际参数 （对应于 a）的函数中分配，不能再加到函数 SequentialSearch 所需要的空间 上去。 再比较下面两个程序，它们都是求已 知数组中元素的和。在第一个程序中 采用累加的办法，而在第二个程序中则采用递归的办法。我们取被累加的元素个 数 n 作为实例特征。在第一个函数中，a，n，i 和 tsum 需要分配空间，与上例 同样的理由，程序所需的空间与 n 无关，因此，S Sum (n)＝0。在第二个程序中， 递归栈空间包括参数 a，n 以及返回地址的空间。对于 a 需要保留一个指针，对 于n则需要保留一个int类型的值。如果假定是near指针（需占用2个字节） ， 返回地址需占用 2 个字节，n 需占用 2 个字节，那么每次调用 Rsum 函数共需 6 个字节。该程序递归深度为 n+1，所以需要 6(n+1)字节的递归栈空间。S Rsum (n) ＝6(n+1)。 累加a[0:n-1] 递归计算a[0:n-1] template<class T> template<class T> 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。可见，递归计算比累加计算需要更多的空间。 上述递归程序的嵌套调用层次 §2 时间复杂性 null 时间复杂性的构成 null 一个程序所占时间T(P)=编辑时间+运行时间； null 编译时间与实例特征无关，而且，一般情况下 ，一个编译过的程序可以 运行若干次，所以，人们主要关注的是运行时间，记做t P (实例特征)； null 如果了解所用编辑器的特征，就可以确定代码 P 进行加、减、乘、除、 比较、读、写等所需的时间，从而得到计算 t P 的公式。令 n 代表实例特 征（这里主要是问题的规模） ，则有如下的表示式： t P (n)=c a ADD(n)+c s SUB(n)+c m MUL(n)+c d DIV(n)+c c CMP(n)+··· 其中，c a ，c s ，c m ，c d ，c c 分别表示一次加、减、乘、除及比较操作所需的时间， 函数ADD，SUB，MUL，DIV，CMP分别表示代码P中所使用的加、减、乘、除及比 较操作的次数； null 一个算术操作所需的时间取决于操作数的类型（int、float、 double 等等） ，所以，有必要对操作按照数据类型进行分类； null 在构思一个程序时，影响 t P 的许多因素还是未知的，所以，在多数情 况下仅仅是对t P 进行估计。 null 估算运行时间的方法：A. 找一个或多个关键 操作，确定这些关键操作 所需要的执行时间（对于前面所列举的四种算术运算及比较操作，一般 被看作是基本操作，并约定所用的时间都是一个单位） ；B. 确定程序总 的执行步数。 null 操作计数 首先选择一种或多种操作（如加、乘和比较等） ，然后计算这些操作分别执 行了多少次。关键操作对时间复杂性影响最大。 Rsum(a, n) Rsum(a, n-1) . . . Rsum(a, 1) Rsum(a, 0) 程序2-2-1 寻找最大元素 template<class T> int Max(T a[], int n) {//寻找a[0:n-1]中的最大元素 int pos=0; for (int i=1; i<n; i++) if (a[pos]<a[i]) pos=i; return pos; } 这里的关键操作是比较。for循环中共进行了n-1次比较。Max还执行了其 它比较，如 for 循环每次比较之前都要比较一 下 i 和 n。此外，Max 还进行 了其他的操作，如初始化 pos、循环控制变量 i 的增量。这些一般都不包含 在估算中，若纳入计数，则操作计数将增加一个常量。 程序2-2-2 n次多项式求值 template<class T> T PolyEval(T coeff[], int n, const T& x) {//计算n次多项式的值，coeff[0:n]为多项式的系数 T y=1, value=coeff[0]; for (int i=1; i<=n; i++) //n循环 {//累加下一项 y*=x; //一次乘法 value+=y*coeff[i]; //一次加法和一次乘法 } return value; } //3n次基本运算 Horner法则： P(x)=(···(c n *x+c n-1 )*x+c n-2 )*x+c n-3 )*x+···)*x+c 0 程序2-2-3 利用Horner法则求多项式的值 template<class T> T Horner(T coeff[], int n, const T& x) {//计算n次多项式的值，coeff[0:n]为多项式的系数 T value=coeff[n]; for(i=1; 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 选择排序 template<class T> template<class T> 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; i<n; i++) for(int size=n; size>1; size--) r[i]=0; //初始化 { int j=Max(a,size); //逐对比较所有的元素 Swap(a[j],a[size-1]); for(int i=1; i<n; i++) } for(int j=0; j<i; j++) } if(a[j]<=a[i]) r[i]++; 其中函数Max定义如程序2-2-1 else r[j]++; 而函数Swap由下述程序给出 } 程序2-2-6 交换两个值 在这两个程序中，关键的操作是 比较。在2-2-4中，对于每个i 的取值，执行比较的次数是i， 总的比较次数为1+2+ … + n-1 =(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) template<class T> inline void Swap(T& a. T& b) {//交 换a和b T temp=a; a=b; b=temp; } 需要执行 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和1 1，不交换；比较 11 和 2，交换。这个行程称为一次冒泡，经一次冒 泡后，原数组变为[3,5,4,7,2,11].可见，数组中最大的数被移动到最右的位置。 下一次冒泡只对数组[3,5,4,7,2 ]进行即可。如此进行下去，最后将原数组按递 增的顺序排列。 程序2-2-7 一次冒泡 程序2-2-8 冒泡排序 template<class T> void Bubble(T a[], int n)void { for(int i=0; i<n; i++) if(a[i]>a[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表示一个程序， 将操作计数 ),,,( 21 kP nnnOL视为实例特征 k nnn ,,, 21 L的函数。令 )(Ioperation P 表示程序实例 I 的操作计数， ),,,( 21 k nnnSL为所讨论程序的 具有实例特征 k nnn ,,, 21 L的实例之集，则 P最好的操作计数为 )},,,(|)(min{),,( 212,1 kPk BC P nnnSIIoperationnnnOLL∈= P最坏的操作计数为 )},,,(|)(max{),,( 212,1 kPk WC P nnnSIIoperationnnnOLL∈= Template<class T> BubbleSort(T a[], int n) { for(int I=n; I>1; I--) Bubble(a, I); } P平均的操作计数为 ∑ ∈ = ),,,( 21 2,1 21 )( |),,,(| 1 ),,( k nnnSI P k k AVG P Ioperation nnnS nnnO L L L P期望的操作计数为 ∑ ∈ ?= ),,,( 2,1 21 )()(),,( k nnnSI Pk AVG P IoperationIpnnnO L L 其中， )(Ip 是实例 I 可被成功解决的概率。 在前面的例子中，一般我们计算的都 是程序的最坏操作计数。如在冒泡程序 Bubble中即是如此。在 顺序搜索 SequentialSearch(T a[], const T& x, int n) 中，取n作为实例特征，关键操作数是比较。此时，比较的次数并不是由n唯一 确定的。若n=100，x=a[0]，那么仅需要执行一次操作；若x不是a中的元素， 则需要执行100次比较。 当x是a 中一员时称为成功查找， 否则称为不成功查找。 每当进行一次不成功的查找，就需要执行n次比较。对于成功的查找，最好的比 较次数是 1，最坏的比较次数为 n。若假定每个实例出现的概率都是相同的，则 成功查找的平均比较次数为 2/)1( 1 1 += ∑ = ni n n i 程序2-2-9 向有序数组插入元素 程序2-2-10 插入排序 template<class T> template<class T> void Insert(T a[], int& n, const T& x) void InsertionSort(T a[], int n) {//向数组a[0:n-1]中插入元素x {//对a[0:n-1]进行排序 //假定a的大小超过n for(int i=1; i<n; i++) { int i; T t =a[i]; for(i=n-1; i>=0 && x<a[i]; i--) Insert(a, i, t); a[i+1]=a[i]; } a[i+1]=x; } n++; //添加了一个元素 } 在程序 2-2-9 中假定： a 中元素在 x 被插入前后都是按递增的顺序排列的 。 我们取初始数组a的大小n作为实例特征， 则程序2-2-9的关键操作 是x与a 中元素的比较。显然，最少的比较次数为1， 这种情况发生在x被插在数组尾部的时候；最多的比较次数是n，发生在x被插 在数组的首部的时候。假定x有相等的机会被插在任何一个可能的位置上。如果 x 最终被插 在 a 的 i+1 处，i>=0,则执行的比较次数是 n-i。如果 x 被插入 a[0] 的位置，则比较的次数为n。所以，平均的比较次数是 )1/(2/ 1 1 )( 1 1 1 1 0 ++= ? ? ? ? ? ? + + = ? ? ? ? ? ? +? + ∑∑ = ? = nnnnj n nin n n j n i 在程序2-2-10中所执行的比较次数， 最好情况下是n-1， 最坏情况下是n(n-1)/2. 虽然在这些简单例子中，我们都给出 了平均操作数，但是在一般情况下，平 均操作数不是很容易求得的，操作数的数学期望值就更不容易求得了。 null 执行步数 利用操计数方法估计程序的时间复杂性注意力集中在“关键操作”上，忽略 了所选择操作之外其他操作的开销。下面所要讲的统计执行步数（step-count） 的方法则要统计程序/函数中所有部分的时间开销。执行步数也是实例特征的函 数，通常做法是选择一些感兴趣的实例特征。如，若要了解程序的运行时间是如 何随着输入数据的个数增加而增加的， 则把执行步数仅看作输入数据的个数的函 数。所谓程序步是一个语法或语意上的程序片断，该片段的执行时间独立于实例 特征。例如 语句：return a+b+b*c+(a+b+c)/(a+b)+4；和 x=y;都可以作为程序 步。一种直观的统计程序执行步数的方法是做 执行步数统计表 矩阵加法程序执行步数统计表 其中s/e表示每执行该语句所要执行的步数。 一条语句的s/e就等于执行该语句 所产生的count值的变化量。频率是指该语句总的执行数。 实际统计中，可以通过创建全局变量count来确定一个程序或函数为完成其 预定任务所需要的执行步数。将count引入到程序语句之中，每当原始程序或函 数中的一条语句被执行时，就为count累加上该语句所需要的执行步数。 程序2-2-11 矩阵加法与执行步数统计 template<class T> void Addm(T **a, T **b, T **c, int rows, int cols) 语 句 s/e 频率 总步数 Void Addm(T **a, ··· ) 0 0 0 { 0 0 0 for(int i=0; i<rows; i++) 1 rows+1 rows+1 for(int j=0; j<cols; j++) 1 rows*(cols+1) rows*cols+rows c[i][j]=a[i][j]+b[i][j]; 1 rows*cols rows*cols } 0 0 0 总 计 2*rows*cols+2*rows+1 {//矩 阵a和b 相加得到矩阵c for(int i=0; i<rows; i++){ count++; //对应于上一条for语句 (共执行了rows步) for(int j=0; j<cols; j++){ count++; //对应于上一条for语句 (共执行了rows×cols步) c[i][j]=a[i][j]+b[i][j]; count++; //对应于赋值语句 (共执行了rows×cols步) } count++; //对应j的最后一次for循环 (共执行了rows步) } count++；//对应i的最后一次for循环 (共执行了1步) } 若取rows和cols为实例特征， 则， 程序2-3-11总的执行步数为 2×rows×cols ＋2×rows＋1。据此，若rows > cols，我们可以通过交换程序中i循环与j循 环的次序而使程序所用时间减少。 §3 渐近符号 确定程序的操作计数和执行步数的目的是为了比较两个完成同一功能的程 序的时间复杂性，预测程序的运行时间随着实 例特征变化的变化量。设 )(nT 是 算法A的复杂性函数。一般说来，当 n单调增加趋于 ∞时， )(nT 也将单调增加 趋于 ∞。 如果存在函数 )( ~ nT ， 使得当 ∞→n 时有 0)(/))( ~ )(( →? nTnTnT ， 则称 )( ~ nT 是 )(nT 当 ∞→n 时的渐近性态，或称 )( ~ nT 是算法A当 ∞→n 的 渐近复杂性。 因为在数学上， )( ~ nT 是 )(nT 当 ∞→n 时的渐近表达式， )( ~ nT 是 )(nT 中略去低阶项所留下的主项， 所以它无疑比 )(nT 来得简单 （举一个例子） 。 进一步分析可知，要比较两个算法的渐近复杂性的阶不相同时，只要确定出 各自的阶，就可以哪一个算法的效率高。换句话说，渐近复杂性分析只要关心 )( ~ nT 的阶就够了，不必关心包含在 )( ~ nT 中的常数因子。所以，我们常常有对 )( ~ nT 的分析进一步简化，即假设算法中用到的所有不同的运算（基本）各执行 一次所需要的时间都是一个单位时间。 综上分析，我们已经给出了简化算法复杂性分析的方法和步骤，即只考虑当 问题的规模充分大时，算法复杂性在渐近意义下的阶。为此引入渐近符号，首先 给出常用的渐近函数。 常 用 的 渐 进 函 数 在下面的讨论中，用f(n)表示一个程序的时间或空间复杂性，它是实例特 征n（一般是输入规模）的函数。由于一个程序的时间或空间需求是一个非负的 实数，我们假定函数f(n)对于n的所有取值均为非负实数，而且还可假定n>=0。 渐近符号 O 的定义 ：f(n)=O(g(n))当且仅当存在正的常数c和 n 0 ，使得对于所有的n>=n 0 ，有f(n)<=cg(n)。此时，称 g(n)是f(n)的一个上界。 函数 f 至多是函数 g 的 c倍，除非 0 nn < 。即是说，当n充分大时， g 是 f 的一个上界函数，在相差一个非零常数倍的情况下。通常情况下，上界函数取单 项的形式，如表1所列。 C 0 =O(1): f(n) 等于非零常数的情形。 3n+2=O(n): 可取c＝4，n 0 ＝2。 100n+6=O(n): 可取 c=101，n 0 ＝6。 10n 2 +4n+3=O(n 2 ): 可取 6×2 n +n 2 =O(2 n ): 可取c =7，n 0 =4. 3×log n + 2×n + n 2 =O(n 2 ). n×log n +n 2 =O(n 2 ). 3n+2=O(n 2 ). 三点注意事项： 1． 用来作比较的函数g(n)应该尽量接近所考虑的函数f(n). 3n+2=O(n 2 ) 松散的界限；3n+2=O(n) 较好的界限。 2． 不要产生错误界限。 n 2 +100n+6， 当n<3时， n 2 +100n+6<106n， 由此就认为n 2 +100n+6＝O(n). 事实上， 对任何正的常数 c，只要 n>c-100 就有 n 2 +100n+6>c×n。同理，3n 2 +4×2 n =O(n 2 ) 函数 名称 函数 名称 1 常数 n 2 平方 log n 对数 n 3 立方 n 线性 2 n 指数 n log n n 倍 long n n！ 阶乘 是错误的界限。 3． f(n)=O(g(n))不能写成g(n)=O(f(n))，因为两者并不等价。 实际上，这里的等号并不是通常相等的含义。按照定义，用集合符号更准确些： O(g(n))={f(n)|f(n)满足： 存在正的常 数c和n 0 ， 使得当n>=n 0 时， f(n)<=cg(n)} 所以，人们常常把f(n)=O(g(n))读作： “f(n)是g(n)的一个大O成员” 。 大 O 比率定理 ： 对于函数 )(nf 和 )(ng ， 如果极限 ))(/)((lim ngnf n ∞→ 存在， 则 ))(()( ngOnf = 当且仅当存在正的常数c，使得 cngnf n ≤ ∞→ ))(/)((lim . 证明：略。 例子 因为 3 23 lim = + ∞→ n n n ，所以 )(23 nOn =+ ； 因为 10 2410 lim 2 2 = ++ ∞→ n nn n ，所以 )(2410 22 nOnn =++ ； 因为 6 2 2*6 lim 2 = + ∞→ n n n n ，所以 )2(2*6 2 nn On =+ ； 因为 0 2 *3 lim 216 = + ∞→ n n nn ，所以 )2(*3 216 n Onn =+ ， 但是这不是一个好的上界估计，问题出在极限值不是正的常数。下述不等式对于 复杂性阶的估非常有帮助： 定理2.3.1 . 对于任意一个正实数 x和 ε，有下面的不等式： 1) 存在某个 0 n 使得对于任何 0 nn ≥ ，有 ε+ < xx nn )(log)(log 。 2) 存在某个 0 n 使得对于任何 0 nn ≥ ，有 nn x <)(log 。 3) 存在某个 0 n 使得对于任何 0 nn ≥ ，有 ε+ < xx nn 。 4) 存在某个 0 n 使得对于任何 0 nn ≥ ，有 nx n 2< 。 5) 对任意实数 y ，存在某个 0 n 使得对于任何 0 nn ≥ ，有 ε+ < xyx nnn )(log 。 例子 根据定理 1，我们很容易得出： )(log 323 nOnnn =+ ； )(log 4205.24 nOnnn =+ ； )2(log/2log2 53534 nOnnnn nnn =＋ 。 符号 ?的定义 ： ))(()( ngnf ?= 当且仅当存在正的常数 c和 0 n ，使得对 于所有的 0 nn ≥ ，有 ))(()( ngcnf ≥ 。 此时 ， 称g(n)是f(n)的一个下界。 函数 f 至少是函数 g 的 c倍，除非 0 nn < 。即是说，当n充分大时， g 是 f 的一个下界函数，在相差一个非零常数倍的情况下。类似于大 O符号，我们可以 参考定理1所列的不等式，来估计复杂性函数的下界，而且有下述判定规则： 大 ?比率定理 ： 对于函数 )(nf 和 )(ng ， 如果极限 ))(/)((lim nfng n ∞→ 存在， 则 ))(()( ngnf ?= 当且仅当存在正的常数c，使得 cnfng n ≤ ∞→ ))(/)((lim . 这里，当 n充分大时， )()( ncfng ≤ 意味着 )( 1 )( ng c nf ≥ ，由此不难看 出上述判别规则的正确性。 符号 Θ的定义 ： ))(()( ngnf Θ= 当且仅当存在正的常数 21 ,cc 和 0 n ，使 得对于所有的 0 nn ≥ ，有 ))(()())(( 21 ngcnfngc ≤≤ 。 此时，称f(n)与g(n) 同阶。 函数 f 介于函数 g 的 1 c 和 2 c 倍之间 ，即当 n充分大时， g 既是 f 的下界， 又是 f 的上界。 例子 );(23 nn Θ=+ )(2410 22 nnn Θ=++ 。 );2(25 2 nn n Θ=+× Θ比率定理 ：对于函数 )(nf 和 )(ng ，如果极限 ))(/)((lim nfng n ∞→ 与 ))(/)((lim ngnf n ∞→ 都存在，则 ))(()( ngnf Θ= 当且仅当存在正的常数 21 ,cc ， 使得 21 ))(/)((lim,))(/)((lim cnfngcnfng nn ≤≤ ∞→∞→ . 比较大 O比率定理和 ?比率定理，可知， ?比率定理实际是那两种情况的 综合。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项，即 定理 2.3.2 . 对于多项式函数 01 1 1 ananana m m m m ++++ ? ? L，如果 0> m a ，则 )()( m nOnf = ， )()( m nnf ?= ， )()( m nnf Θ= 。 一般情况下， 我们不能对每个复杂性函数去估计它们的上界、 下界和 “双界” ， 前面定理1和定理2给了一些直接确定这些界的阶函数（或叫渐近函数）的参考 信息。下面将要给出由多个函数经过加、乘运算组合起来的复杂函数的阶的估计 方法。首先引进如下记号 小 o 符号定义 ： ))(()( ngonf = 当且仅当 ))(()( ngOnf = 和 ))(()( nfOng ≠ 。 例子： )(32)( nnnt sum Θ=+= ； )(122),( mnnmnnmt Add Θ=++= ； )()3)(1(2/)7()( nnnnt AVG SeachSequential Θ=+?++= αα ，其中表示被查元素 x在数组 a中的概率。 最后给出折半搜索程序及算法复杂性估计. 程序2-3-1 折半搜索 template<class T> int BinarySearch(T a[], const T& x, int n) {//在a[0]<=a[1]<=···<=a[n-1]中搜索x //如果找到，则返回所在位置，否则返回 –1 int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到x } while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该 循环在最坏的情况下需要执行 )(lognΘ 次。由于每次循环需耗时 )1(Θ ，因此在 最坏情况下，总的时间复杂性为 )(lognΘ 。