第二章复杂性分析初步 程序性能( 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+· T temp=a; a=b; b= +n-1= 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); }
平均的操作计数为 O(nn2…,n2)= ∑ operation2() S(n1,n2…,n)|ls(m) P期望的操作计数为 O(mn2…,n1)=∑p()· operation2() eS(n,n2;…,nk) 其中,p(1)是实例Ⅰ可被成功解决的概率 在前面的例子中,一般我们计算的都是程序的最坏操作计数。如在冒泡程序 Bubble中即是如此。在顺序搜索 Sequentialsearch(Ta[], const t&x,intn) 中,取n作为实例特征,关键操作数是比较。此时,比较的次数并不是由n唯 确定的。若n=100,x=a[0],那么仅需要执行一次操作;若x不是a中的元素 则需要执行100次比较。当x是a中一员时称为成功查找,否则称为不成功查找 每当进行一次不成功的查找,就需要执行n次比较。对于成功的查找,最好的比 较次数是1,最坏的比较次数为n。若假定每个实例出现的概率都是相同的,则 成功查找的平均比较次数为 ∑i=(n+1)/2 再考察插入排序算法 程序2-2-9向有序数组插入元素 程序2-2-10插入排序 templateclass T> templateclass t> void Insert(t a, int& n, const T& x) void InsertionSort(t ad, int n) /向数组a[0:n-1]中插入元素x /对a[0:n-1进行排序 /假定a的大小超过n for (int i=l: i=0&&x=0,则执行的比较次数是n-i。如果x被插入a[0]
P 平均的操作计数为 ∑ ∈ = ( , , , ) 1 2 1, 2 1 2 ( ) | ( , , , ) | 1 ( , , ) S n n nk I P k k AVG P operation I S n n n O n n n L L L P 期望的操作计数为 ∑ ∈ = ⋅ ( , , , ) 1, 2 1 2 ( , , ) ( ) ( ) S n n nk I k P AVG P O n n n p I operation I L L 其中， p(I)是实例 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。若假定每个实例出现的概率都是相同的，则 成功查找的平均比较次数为 ( 1)/ 2 1 1 ∑ = + = i n n n i 再考察插入排序算法： 程序 2-2-9 向有序数组插入元素 程序 2-2-10 插入排序 template template 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=0 && x=0,则执行的比较次数是 n-i。如果 x 被插入 a[0]
的位置,则比较的次数为n。所以,平均的比较次数是 1(∑(n-1)+n ∑j+n|=n/2+n/(n+1) n+1 在程序2-2-10中所执行的比较次数,最好情况下是n-1,最坏情况下是n(n-1)/2. 虽然在这些简单例子中,我们都给出了平均操作数,但是在一般情况下,平 均操作数不是很容易求得的,操作数的数学期望值就更不容易求得了 执行步数 利用操计数方法估计程序的时间复杂性注意力集中在“关键操作”上,忽略 了所选择操作之外其他操作的开销。下面所要讲的统计执行步数(step- count) 的方法则要统计程序/函数中所有部分的时间开销。执行步数也是实例特征的函 数,通常做法是选择一些感兴趣的实例特征。如,若要了解程序的运行时间是如 何随着输入数据的个数增加而增加的,则把执行步数仅看作输入数据的个数的函 数。所谓程序步是一个语法或语意上的程序片断,该片段的执行时间独立于实例 特征。例如语句: return a+b+b*c+(a+b+c)/(a+b)+4;和x=y;都可以作为程序 步。一种直观的统计程序执行步数的方法是做执行步数统计表 矩阵加法程序执行步数统计表 s/e频 步 Void addm(T**a,…) 00 0 for(int i=0; i*a, T **b, T **c, int rows, int cols
的位置，则比较的次数为 n。所以，平均的比较次数是 / 2 /( 1) 1 1 ( ) 1 1 1 1 0 = + + + + = − + + ∑ ∑= − = j n n n n n n i n n n j n i 在程序 2-2-10中所执行的比较次数，最好情况下是 n-1，最坏情况下是 n(n-1)/2. 虽然在这些简单例子中，我们都给出了平均操作数，但是在一般情况下，平 均操作数不是很容易求得的，操作数的数学期望值就更不容易求得了。 z 执行步数 利用操计数方法估计程序的时间复杂性注意力集中在“关键操作”上，忽略 了所选择操作之外其他操作的开销。下面所要讲的统计执行步数（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 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