程序性能分析

1、7月-221第二章程序性能分析2.1概述2.2空间复杂度2.3时间复杂度2.4渐进符号7月-222第二章程序性能分析本章所介绍的程序性能分析和测量的概念涉及以下内容：确定一个程序对内存及时间的需求使用操作计数和执行步数来测量一个程序的时间需求。使用渐进符号来描述复杂性 (O、o)利用计时函数测量一个程序的实际运行时间。7月-223排序的基本概念排序的定义简单定义：排序是按照关键字的非递减或非递增顺序对一组记录重新进行整队（或排列）的操作。数学定义：假设含有n个记录的序列为： r1, r2, ,rn (a-1)它们的关键字相应为k1, k2, ,kn,对式(a-1)的记录序列进行排序就是要确定序

2、号1,2, ,n的一种排列p1, p2,pn使其相应的关键字满足如下的非递减(增)关系： kp1 kp2 kpn (a-2)也就是使式(a-2)的记录序列重新排列成一个按关键字有序的序列 rp1 rp2 rpn (a-3)7月-224排序的基本概念排序的目的是什么？便于查找排序算法的好坏如何衡量？时间效率排序速度（即排序所花费的全部比较次数）空间效率占内存辅助空间的大小稳定性若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。7月-225排序的基本概念排序的特性稳定性与不稳定性当待排记录中的关键字ki(1,2,n)都不相同时，则任何一个记录的无序序列经排

3、序后得到的结果是惟一的。简单地说，稳定性排序-数据排序过后能使值相同的数据，保持原顺序中之相对位置。反之，则称为“不稳定性排序” 。若排序的序列中存在两个或两个以上关键字相等的记录时，则排序得到的记录序列的结果不惟一。假设ki= kj (1i n, 1jn, ij )，且在排序前的序列中 ri 领先于rj (即ij ) 。若在排序后的序列中ri 总是领先于rj ，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中 rj领先于ri ，则称所用的排序方法是不稳定的。7月-226排序的基本概念27169（1）317249（2）1701234567 排序前：79（1）9（2）1617242731

4、01234567 稳定排序：79（2）9（1）161724273101234567 不稳定排序：7月-227排序的基本概念根据在排序的过程涉及的存储器不同，排序方法可分为两类：1.内部排序（Internal Sort）：在排序进行的过程中不使用计算机外部存储器的排序过程。选择排序、插入排序、冒泡排序、计数排序快速排序、归并排序、希尔排序堆排序、基数排序2. 外部排序（External Sort）：在排序进行的过程中需要堆外存进行访问的排序过程。7月-228排序的基本概念内部排序的过程是一个逐步扩大记录的有序序列的过程。通常在排序的过程中，参与排序的记录序列可划分两个区域：有序序列区和无序序列区

5、，其中有序序列区的的记录已按关键字非递减有序排列。使有序序列中记录的数目至少增加一个的操作称为一趟排序。7月-229排序的基本概念思想：在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次小的记录、，并分别有序序列中的第1个位置、第2个位置、，最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到大排列的的有序序列。有序序列 R1.i-1无序序列 Ri.n有序序列 R1.i-1RjRi有序序列 R1.i无序序列 Ri+1.n一趟排序后一趟排序开始7月-22102.1Introduction由于每个人编写的程序各有各的风格，通常很

6、难判断好坏。可以作为判断的标准的应是“程序运行的效率”，也就是程序性能。我们所说的“程序运行的效率”是指在程序正确执行的前提下，所用的时间最少、空间最少。但是“时间”与“空间”常常是“鱼与熊掌”无法兼得，如果希望以最短的时间来完成该程序，则常常需要运用更多的存储空间，来换取最短的执行时间；如果希望以最小的存储空间来完成该程序，相反的也必须用较久的时间，才能完成该程序。7月-22112.1Introduction所谓程序性能(Program Performance)，是指运行一个程序所需要的内存大小和时间。可以采用两种方法来确定一个程序的性能，一个是分析的方法，一个是实验的方法。在性能分析(Pe

7、rformance analysis)时，采用分析的方法(对时间而言也称为Priori-Estimate事前预测)。在性能测量(Performance measurement)时，借助于实验的方法(对时间而言也称为Posteriori Testing事后测试)7月-2212空间复杂性(space complexity) 是指运行一个程序所需要的内存大小。1. 我们对一个程序的空间复杂性感兴趣的主要原因如下：如果程序运行在多用户系统上，通常需要指明分配给该程序内存的大小。对任何的计算机系统都有内存的限制，通过分析我们可以事先知道是否有足够的内存来运行该程序。一个问题可能有不同的内存解决方案；(不

8、同的编译器所需内存不同)。可以利用空间复杂度来估算一个程序所能解决问题的最大规模；如电路模拟程序，模拟一个有C个元件、W个连线的电路，需要内存为280K+10*(C+W)字节的内存。如果可用内存总量为640K，则最大可模拟的规模为C+W36K的电路。2.2 Space Complexity7月-22132. 空间复杂性的组成：指令空间(instruction space)是指用来存储经过编译之后的程序指令所需的空间。数据空间(data space)是指用来存储所有常量和所有变量值所需的空间。数据空间由两部分组成：存储常量和简单变量、存储复合变量。环境栈空间(environment stack

9、space)用来保存函数调用时为恢复程序继续运行的有关信息所需的存储空间。2.2 Space Complexity7月-22142.2 Space Complexity2.1) 指令空间：程序所需要的指令空间的大小取决于以下因素把程序编译成机器代码的编译器。编译时实际采用的编译器选项。如优化选项、对齐选项、覆盖选项等。目标计算机。如有无浮点处理器。7月-22152.2 Space Complexity2.2) 数据空间：对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量和常量的数目。我们关心的是数据的字节数，每种数据类型所占的字节数与机器和编译器有关。对于复合变量，需要进

10、行计算。如：double a100和int mazerowscols对于32位元机器及32位元编译器所站存储空间分别为8*100和4*rows*colsTypeSpace(byte)Rangechar1-128 127 (-27 27-1 )unsigned char10 255 ( 0 28-1 )short2-32768 32767 (-215 215-1 )int4-231 231-1 unsigned int40 65535 ( 0 216-1 )long4-231 231-1unsigned long40 232-1float43.4E38double81.7E308long dou

11、ble103.4E-4932 1.1E+4932pointer2near pointer/Segment Regpointer4far pointer7月-22162.2 Space Complexity2.3) 环境栈空间：对于刚开始做性能分析的人，本部分常常容易被乎略，原因是他们不理解函数是如何被调用的及在函数被调用结束后发生了什么。每当一个函数被调用时，下面的数据将被保留在环境栈中：所有引用参数及常量引用参数的定义。返回地址。函数被调用时所有局部变量的值以及传值形式参数的值（对某些编译器：仅对于递归函数而言）。7月-22172.2 Space Complexity2.4) Summary

12、:程序所需要的空间取决于多种因素，有些因素在编写程序时是未知的。即使这些因素已完全知道，我们也无法精确的分析一个程序所需要的空间。但是，我们可以确定程序某些部分对空间的需求，这些部分依赖于所解决问题实例的特征。一般来说，这些特征包含决定问题规模的那些因素；如输入输出的数量等。例如对n个元素排序，两个nXn矩阵的加法，我们可以把n作为特征。7月-22182.2 Space Complexity任意程序P所需空间S(P)可以表示如下：S(P)=c + Sp(实例特征)其中c是一个常数，表示固定部分所需要的空间。Sp表示可变部分所需要的空间。固定部分，它独立于实例的特征，一般来说它包含指令空间、简单

13、变量及定长复合变量的空间和常量空间。可变部分，它由以下部分组成：复合变量所需的空间（其大小依赖于解决问题的规模），动态分配的空间（通常依赖于实例的特征），以及递归栈所需的空间递归栈空间包括递归深度（即嵌套递归调用的最大层次）、局部变量和形参的空间。7月-22192.2 Space ComplexityS(P)=c + Sp(实例特征)；在分析程序空间复杂度时，我们将主要精力放在估算Sp上。对于任意给定的问题，首先需要确定实例的特征，以便于估算空间需求。实例特征的选择是一个很具体的问题，我们将通过实际例子来说明。实例特征说明：指令空间：与实例特征无关的常数数据空间：常量和简单变量-实例无关复合变

14、量(数组、链表、树和图等) -问题实例特征有关环境栈空间(函数调用)-是否递归?非递归：实例特征无关递归：实例特征相关在分析空间复杂度时我们忽略与实例特征无关的空间需求量7月-22202.2 Space ComplexityS(P)=c + Sp(实例特征)；例2-1：程序1-4SAbc(传值T) =3*sizeof(T);（动态空间分配） SAbc(引用T)=0; SAbc(abc的大小)=0;template T Abc(T& a, T& b, T& c)return a+b+b*c+(a+b-c)/(a+b)+4；/程序1-4template T Abc(T a, T b, T c) ；

15、/程序1-47月-22212.2 Space Complexity例2-2：顺序搜索template int SequentialSearch(T a, const T& x, int n)/在无序数组a0 :n-1中搜索x; 如找到返回其位置int i;for (i=0; in & ai !=x; i+) ;if (i=n) return -1; return i;/程序1-4选实例特征n: S顺序搜索(n)=0；(数组空间在在调用函数中分配)实例特征如何选择？空间复杂度？7月-22222.2 Space ComplexitySsum(n)=0；SRsum(n)=(Addr +sizeof(

16、int)+sizeof(ptr) )*(n+1)SFactorial(n)=(Addr +sizeof(int) )*Maxn,1Template T Sum(T a, int n)/计算a0:n-1的和T tsum=0;for (int i=0; in; i+)tsum+=ai;return tsum; /程序1-8Template T Rsum(T a, int n)/递归计算a0:n-1的和if (n0) return Rsum(a,n-1)+an-1; return 0; /程序1-9int Factorial(int n)/递归计算n!if (n =1) return 1;else

17、return n* Factorial(n-1); /程序1-77月-2223空间复杂度小结对非递归算法分析与实例特征有关的数据结构的大小复合变量对递归算法还要分析递归调用的深度和实例特征的关系环境栈地址参数变量(类型、地址)复合变量 (数组、指针、结构)递归深度7月-22242.3Time Complexity时间复杂性(time complexity) 是指运行完该程序所需要的时间。1. 我们对一个程序的时间复杂性感兴趣的主要原因如下：有些计算机需要用户提供程序运行时间的上限，一旦达到时间上限，程序将被强制结束。正在开发的程序可能需要提供一个满意的实时响应。如交互程序、通讯程序。如果有多种

18、可选的方案来解决一个问题，那么具体决定采用哪个？时间是一个重要的因素。对于各种解决方案的时间及空间复杂性将采用加权的方式进行评估。7月-22252.3Time Complexity2. 时间复杂度的组成影响一个程序空间复杂性的因素也都能影响程序的时间复杂性。一个程序所占的时间T(P)=编译时间+运行时间。由于编译时间和实例特征无关，我们关注的程序运行时间，记做tp(实例特征)如果我们了解编译器的特性，并且清楚运行的环境，我们就可以对程序P进行加、减、乘、除、比较、读、写等操作进行计算，从而可以得到如下公式：7月-22262.3Time Complexitytp(n)=caADD(n)+ csS

19、UB(n)+ cmMUL(n)+其中ca、cs、cm为一个加法、减法、乘法的时间，函数ADD、SUB、MUL为相应运算的次数。有两个更可行的方法可用来估算运行时间：找出一个或多个关键操作，确定关键操作所需的执行时间(操作计数)。确定程序总的执行步数。7月-22272.3Time Complexity3. 操作计数(Operation Counts)估算一个程序或函数的时间复杂性的一种方式就是首先选择一种或多种操作（如加、减、乘），然后确定这种操作分别执行了多少次。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。让我们先看看实际的例子（根据例子具体学习）例2-8多项

20、式求值多项式P(x) = i=0ncixi, 如果cn0，则P是一个n维多项式。7月-22282.3Time ComplexityTemplate T ProcA(T coef,int n, const T& x)/计算n次多项式的值 coef0 :n为多项式的系数T y=1, value= coef0;for (i=1; i=n; i+) y*=x;value+=y*coefi;return value;/程序2-3Template T ProcB(T coef,int n, const T& x)/计算n次多项式的值 coef0 :n为多项式的系数T y=1, value= coefn;f

21、or (i=1; i=n; i+) value=value*x+coefn-i;return value;/程序2-4算法基于多项式分解：P(x) =(cnx + cn-1)*x + cn-2)*x + )*x + c0ProcA 执行了 n 次加法；2n次乘法；ProcB 执行了 n 次加法；n次乘法；7月-22292.3Time Complexity例2-9计算名次元素在队列中的名次(rank)，可定义为队列中所有比它小的元素再加上它左面和它相同的元素数目。如数组a=4,3,9,3,7作为队列，则各个元素的名次为r=2,0,4,1,3。如何设计程序？复杂度为(n-1)n/2Template

22、 void Rank(T a, int n, int r)/计算a0 :n-1中n个元素的排名for (int i=0; in; i+) ri=0;/初始化/逐个比较所有元素for (i=1; in; i+) for (int j=0; ji; j+) if(aj =ai) ri+;else rj+;/程序2-5；a 4 3 9 3 7 对于i的每个取值，执行i次比较。总比较次数：1+2+。+n-1i=1 1 0i=2 1 0 2i=3 2 0 3 1i=4 2 0 4 1 37月-22302.3Time Complexity例2-10计数排序在使用rank排名后，就可按递增的顺序对数组进行重

23、新排序我们使用附加数组u,来进行排序Rearrangs的复杂度为2n这种用程序2-5和2-6排序的方法称为计数排序（Rank sort)复杂度(n-1)n/2+2nTemplate void Rearrangs(T a, int n int r)/按序重排数组a中的元素，T *u = new Tn+1; /辅助数组u/在u中移动到正确位置for (int i=0; in; i+) uri=ai;/move back to afor (i=0; in; i+) ai=ui;delete u;/程序2-6；7月-22312.3Time Complexity例2-11选择排序初始状态49138654

24、9276132752i=1133865492764912752i=2132765492764913852i=3132738492764916552i=4132738492764916552i=5132738492491655276i=6132738492491657652i=71327384924916576527月-22322.3Time Complexity例2-11选择排序思路为选择最小的数放在最前面；在剩下的元素重复此步骤。每个Min的比较次数为n-size-1;总的次数为 (n-1)n/2移动次数为3(n-1) 选择排序的复杂度为(n-1)n/2+ 3(n-1)Template vo

25、id SelectionSort(T a, int n)/对数组a0 :n-1中的元素进行排序for (int size=0; sizen-1; size+) int j=Min(a, size, n); Swap(aj, asize);/程序2-7；Template Int Max (T a, int n)/Locate the largest element in a0:n-l int pos = 0;for (int i=0; in; i+) if (aposai) pos = i;return pos; /program1-31；7月-22332.3Time Complexity例2-

26、12冒泡排序37968548549637968963754896548377月-22342.3Time Complexity例2-12冒泡排序是一种简单的排序方法，思路为把最大的元素移到右部。在冒泡过程中，对相临的元素进行比较，如果左边的元素大，左右交换。在一趟冒泡排序中最大的 元素一定在最右边。元素比较次数为 (n-1)n/2，与选择排序相同Template void Bubble(T a, int n)/把数组a0 :n-1中最大的元素通过冒泡移动到右边（一次冒泡）for (int i=0; i ai+1) Swap(ai,ai+1);/程序2-8；Template void Bubble

27、Sort(T a, int n)/把数组a0 :n-1中的n个元素进行冒泡排序for (int i=n; i 1; i-) Bubble( a, i );/程序2-9；7月-22352.3Time Complexity通过已给出的例子我们知道时间复杂度和输入数据有关，也就是实例的特征较为简单，操作计数都是这些特征的良性函数(nice function)。如果我们加入一些其它特性，问题就会变得很复杂，例如Bobble所执行的交换次数不仅依赖于n，而且还依赖于数组a中的具体情况。交换次数在0n-1之间变化。由于操作数不总是由所选定的实例特征唯一确定；我们会提出最好的、最坏的操作数是多少？下面我们来

28、讨论这个问题。7月-22362.3Time Complexity例2-15再看计数排序：在已经使用Rank计算出数组中元素的名次后，我们可以在原地进行排序。方法是如果ri!=i；把ai和ari进行交换；交换的结果是把ai放到该放的位置。该程序最少执行了0次交换，最大2(n-1)次交换。因为每次交换需三次移动，所以该程序的最坏情况，时间增加，但节省了内存。Template void Rearrangs(T a, int n int r)/原地重排数组a中的元素for (int i=0; in; i+) while( ri!=i ) /获得应该排在ai处的元素 int t = ri; Swap(

29、ai, at ); Swap( ri, rt ); /程序2-11；4393720413i: ri:ai:0123494423904391479347月-22372.3Time Complexity例2-16再看选择排序：前面的选择排序有一个缺点，即使元素已经排序它还在继续执行。改进方法是在查找最大元素时，顺便检查数组是否已经排序。最好情况外循环仅执行1次；a中元素进行了n-1次比较。最坏情况执行的比较次数为(n-1)n/2。最坏与原程序一样。Template void SelectionSort(T a, int n)/及时终止选择排序bool sorted = false;for (int

30、 size=n; !sorted & (size1); size-) int pos = 0 sorted = true; for ( int i=1; i size; i+) /找最大元素 if (apos =ai) pos= i; /判定是否已为递增排序 else sorted = false; /未按序排列 Swap(apos, asize-1);/程序2-12；7月-22382.3Time Complexity例2-17再看冒泡排序：我们同样可以参考选择排序的方法，可以设计一个及时的终止冒泡排序函数。改进方法是在冒泡中没有交换，就可以终止冒泡过程。最好情况比较次数为n-1，最坏和原来一

31、样。Template bool Bubble(T a, int n)/把数组a0 :n-1中最大的元素冒泡至右端bool swapped = false;for (int i=0; i ai+1) Swap(ai,ai+1);swapped = true; return swapped;void BubbleSort(T a, int n)/及时终止冒泡排序for (int i=n; i 1 & Bubble( a, i ); i-);/程序2-13；7月-22392.3Time Complexity插入排序初始状态491386597761327492i=2i=3i=4i=5i=6i=7i=8

32、3849165977613274923849165977613274923865491659776132749238974916576971327492387649138657697274921313491273865769749213274912738976576492134927月-22402.3Time Complexity例2-18插入排序：我们可以以Insert函数为基础，设计一个排序程序。我们知道如果只有一个元素的数组，是有序数组。这时再插入数据也是有序数组。最好情况比较次数为n-1，最坏为(n-1)n/2Template void Insert(T a, int & n, con

33、st T& x)/向有序数组a0 :n-1中插入元素xfor (int i=n-1; i=0 & x ai; i-) ai+1=ai;ai+1=x;void InsertionSort(T a, int n)/对a0 :n-1进行排序for (int i=1; in; i+) T t=ai; Insert(a, i, t);/程序2-14； 2-15是把两个函数合一7月-22412.3Time Complexity4. 执行步数(step-count)利用操作计数方法来估算程序的时间复杂性时，忽略了所选操作计数以外的其它操作的开销。执行步数(step-count) 统计程序或函数中全部的时间开

34、销。与操作计数一样，执行步数也是实例特征的函数。尽管对特定的程序可能会有若干个特征（如输入输出的个数和大小），但可以把执行步数看成是其中一部分特征的函数。语句频度7月-22422.3Time Complexity在确定一个程序的执行步数之前，必须确切地知道将要采用的实例特征。这些特征不仅定义了执行步数表达式中的变量，而且定义了以多少次计算作为一步。在选择了实例特征后，可以定义一个操作步(step). 操作步是独立于所选特征的任意计算单位。如100次乘法可视为一步；但n次乘法不能视为一步，因为n是实例特征。同样，在包含实例特征的多次计算不能算成是一步。7月-22432.3Time Complex

35、ity定义程序步程序步(program step)可以定义为一个语法或语义意义上的程序片段，该片段独立于实例特征。如 return a+b+b*c+(a+b+c)/(a+b)+4;可以被视为一个程序步。同样 x=y; 也可以被视为一个程序步。我们可以使用初值为0的全局变量count来确定一个程序或函数为完成预定任务所需的执行步数。可以count引入到程序中，每当原程序的一条语句被执行，就在count上累加该语句的执行步数。当程序结束时count的值就是所需的执行步数。7月-22442.3Time Complexity例2-19 把count引入到函数Sum(1-8)问执行步数是多少？执行步数为

36、2n+3;templateT Sum(T a, int n)/ Return sum of numbers a0:n - 1. T tsum = 0; count+; / for tsum = 0 for (int i = 0; i n; i+) count+; / for the for statement tsum += ai; count+; / for assignment count+; / for last execution of for count+; / for return return tsum;/程序2-167月-22452.3Time Complexity例2-20

37、把count引入到递归函数Rsum (1-9)templateT Rsum(T a, int n)/ Return sum of numbers a0:n - 1. count+; / for if conditional if (n 0) count+; / for return return Rsum(a, n-1) + an-1; count+; / for return return 0;/程序2-18令tRsum(n)为执行步数，我们知道tRsum(0)=2tRsum(n)=2+tRsum(n-1)，n0;上式为递归等式。计算后得到tRsum(n)=2n+tRsum(0)=2(n+1

38、)我们注意到Rsum的执行步数小于Sum,但由于执行步数不是精确时间，目前还无法确定他们谁快。7月-22462.3Time Complexity例2-21矩阵加 执行步数为2rows*cols+2rows+1;问题：如果rows比cols大，怎样修改程序？templatevoid Add( T *a, T *b, T *c, int rows, int cols)/ Add matrices a and b to obtain matrix c. for (int i = 0; i rows; i+) for (int j = 0; j cols; j+) cij = aij + bij;/程

39、序2-19templatevoid Add( T *a, T *b, T *c, int rows, int cols)/ Add matrices a and b to obtain matrix c. for (int i = 0; i rows; i+) count+; / preceding for loop, rows for (int j = 0; j cols; j+) count+; / preceding for loop, rows*cols cij = aij + bij; count+; / assignment, rows*cols count+; / last ti

40、me of j for loop, rows count+; / last time of i for loop, 17月-22472.3Time Complexity我们也可以不使用count计数；而是建立一张表，在该表中列出每条语句所需要的执行步数。在建立该表时，我们先确定该语句每一次执行所需步数（记为s/e)以及该语句总的执行次数（频率）。利用这两个量就可以确定每条语句的执行步数。把所有语句相加就得到程序执行步数。注意：一条语句的程序步数与该语句每次执行所需步数有重要的区别，区别在于程序步数不能反映该语句的复杂程度。如 x=Sum(a,m)的程序步数为1，但该语句的导致count的变化为

41、1+2m+37月-22482.3Time Complexity语 句s/e频率总步数T Sum(T a, int n)/ Return sum of a0:n -1. T tsum = 0; for (int i = 0; i 0) return Rsum(a, n-1)+an-1;return 0;00111000n+1n1000n+1n10总 计2n+27月-22492.3Time Complexity在某些情况，一条语句每次执行所需要的执行步数可能随时发生变化。例如计算数组元素的和:i=0jai 对于j=0,1,n-1我们已知Sum(a,n)的执行步数为2n+3,在函数中的步数为2j+6

42、;该函数总的执行步数为:j=0n-1(2j+6)=n(n+5)语 句s/e频率总步数void Inef(T a, T b, int n)/ Compute prefix sums. for (int j = 0; j n; j+) bj = Sum(a, j + 1);0012j+6000n+1n000n+1n(n+5)0总 计n2+6n+17月-22502.3Time Complexity语 句s/e频率总步数int SequentialSearch(T a, T& x, int n)/顺序搜索最坏情况 int i; for (i = 0; i n & ai != x; i+); if (i

43、 = n) return -1; return i;0011110001n+1100001n+1100总 计n+3语 句s/e频率总步数int SequentialSearch(T a, T& x, int n)/顺序搜索最好情况 int i; for (i = 0; i 0 ,则f(n)=O(nm)证明: f (n) i=0m|ai|ni nmi=0m|ai|ni-m nmi=0m|ai|7月-22552.4Asymptotic Notation例2-24、线性函数：f(n)=3n+2; f(n)=O(n)例2-25、平方函数：f(n)=10n2+4n+2; f(n)=O(n2)例2-26、

44、指数函数：f(n)=6*2n+n2; f(n)=O(2n)例2-27、常数函数：f(n)=2345; f(n)=O(1)例2-28、松散界限：10n+8=O(n2);6n2n+20=O(n22n ) 显然、它们不是最小上限。例2-29、错误界限：3n+2O(1);2n2+4nO(n) 反证法证明不符合定义。（见书P57）7月-22562.4Asymptotic Notation2. 符号(渐进紧密下限)符号，用来估算函数f的下限值定义:符号 f (n)=(g(n) 当且仅当存在正的常数c和n0,使得对所有的nn0 ,有 f (n) cg(n) 定理1: 如果f(n)=amnm+a1n+a0 ,

45、且am0 ,则f(n)=(nm)7月-22572.4Asymptotic Notation3. 符号(渐进紧密限度)符号适用于同一个函数既可作为函数f的上限也可以作为f的下限的情形定义:符号 f (n)=(g(n) 当且仅当存在正的常数c1，c2和某个n0,使得对所有的nn0 ,有 c2g(n) f(n) c1g(n) 定理1: 如果f(n)=amnm+a1n+a0 ,且am0 ,则f(n)= (nm)7月-22582.4Asymptotic Notation4. 小写o符号(非紧密上限)小写o符号，用来估算函数f的下限值定义:小写o f (n)=o(g(n) 当且仅当f(n)=O(g(n)

46、且 f(n)(g(n)例：计算3n+2 的小写o 3n+2=O(n2) , 3n+2=(n) and 3n+2(n2) 3n+2=o(n2) but 3n+2o(n) 同样我们可以定义小写符号(非紧密下限)7月-22592.4Asymptotic Notation5.1 关于渐进符号的其它定理定理：对于任一个实数x0和任一个实数0下面的结论都是正确的：1) 存在某个n0使得对于任何nn0 ,有(logn)x(logn)x+。2) 存在某个n0使得对于任何nn0 ,有(logn)x n3) 存在某个n0使得对于任何nn0 ,有nx nx+。4) 对于任意实数y，存在某个n0使得对于任何nn0 ,

47、 有nx(logn)y nx+ 。5) 存在某个n0使得对于任何nn0 ,有nx1) (rn)E7:n! (n/e)n)E8:ni=1 1/i (log n)7月-22612.4Asymptotic Notation5.3 实用的规则S1: if b1 and a1 then logan (logbn) S2: if ba0 then an o(bn)S3: if a0 then logn o(an)S4: if a0 then an o(n!)S5: if ab then na O(nb)S6: if a0 and b1 then na o(bn)S7: if limnf (n)/g (n)

48、=c then f(n) (g(n) if limnf (n)/g (n)=0 then f(n) o(g(n) if limnf (n)/g (n)= then g(n) o(f(n) 7月-22622.4Asymptotic Notation6 复杂性分析举例我们已经学习了渐进符号的表示方法和他们的一些定理和公式。在不需要精确确定执行步数的情况下，可以应用渐进符号来分析本章第三节关于执行步数的情况。我们把使用渐进符号表示有关执行步数的时间复杂性称为渐进复杂性。语 句s/e频率总步数T Sum(T a, int n)/ Return sum of a0:n -1. T tsum = 0; for (int i = 0; i n; i+) tsum += ai; return tsum;0011110001n+1n10(0)(0)(1)(n)(n