第二章复杂性分析初步 程序性能( 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 < class T > 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< class t> int SequentialSearch (T al,\ const T& x, int n /在a[0:n-1]中搜索x,若找到则//回所在的位置,否则返回-1 int 1 for(i=0: i<n & ali=!x: i++) f (i==n return -1 return 1 在程序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无关,因此,Ss=(m)=0。在第二个程序中, 递归栈空间包括参数a,n以及返回地址的空间。对于a需要保留一个指针,对 于n则需要保留一个int类型的值。如果假定是near指针(需占用2个字节), 返回地址需占用2个字节,n需占用2个字节,那么每次调用Rsum函数共需6 个字节。该程序递归深度为n+1,所以需要6(n+1)字节的递归栈空间。Sau(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) 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 < 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 无关，因此，SSum(n)＝0。在第二个程序中， 递归栈空间包括参数 a，n 以及返回地址的空间。对于 a 需要保留一个指针，对 于 n 则需要保留一个 int 类型的值。如果假定是 near 指针（需占用 2 个字节）， 返回地址需占用 2 个字节，n 需占用 2 个字节，那么每次调用 Rsum 函数共需 6 个字节。该程序递归深度为 n+1，所以需要 6(n+1)字节的递归栈空间。SRsum(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。可见,递归计算比累加计算需要更多的空间。 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)