51.5性能分析 19 例1.6函数abc(见程序1.10)的输入是二个简单变，输出返问一个简单变敏。根据以上分 类，这个函数只有定长空间需求，因此，Sabc(I)=0。 ◇ float abc(float a,float b,float c) return a+b+b+c+(a+b-c)/(a+b)+4.00; 程序110简单草术品教 例1.7程序111的输山只有一个简单变量，但输入比上例增加了一个数组，这里，变长空间 需求依赖于数组参革是如何传给函数的。不同语言的处理各不相同，对丁Pascal语言，数组 参革是按值传送，就是说，这个函数在执行时，整个数组被复制到函数的临时存储空间。对 应这样一类语言，程序1.11的变长空间需求是Sum(I)=Sum(m)=,n是数组长度。C 言的参数传递方法显然也是传值调用，但如果传递的是数组参量，C只传递数组第一个 的首地址，并不复制整个数组，因而，Sum(n)=0。 ◇ float sum(float list[],int n) float tempsum=0; 1nt1; for (i 0:ic ni it+) tempsum+=1ist【a return tempsum; 程序1.11数组求和的循环实现 例1.8程序1.12也是增加了一个数组，不过这个求和程序是递归程序，编译器要为每次递 归调用保存参其、局部变革、返可地址。 float sum(float list []int n) ig (n)return rsum(list,n-1)+list [n-1]; return 0; 程序1.12数组求和的递归实现 本例中，一次递归调用所需的空间是两个参量的学节数加上返同地址的字节数。假定整 数和指针所需字节数都是4，图1.1示出每次递归调州所需的字节数
§】。5性 能分析 例 1.6函 数 abc(见 稆序 1.10)的 输入足I个 简唯变鞋, 类,这 个函数只有定长空问需求,lkl此 ,%bc(Ⅰ )=0° 19 输 出 返 lnl~个 简 单 变 蚩 。根 据 以 上 分 □ float abc (float a, float b, float c ) t return a+b+b*c+ (a+b- c) / (a+b) +4 . 0 0 ; 程序 1.10简 单算术函数 例 1.7程 序 1.11的 输出只有 一个简单变章,但 输入比上例增加了 一个数细,这 里,变 长空间 需求依赖于数组参蚩是如何传给函数的。不同语言的处理各不相同,对 丁Pascal语 言,数 组 参童是按值传送,就 足说,这 个函数在执行时,整 个数组被复制到函数的临时存储空间。对 应这样 一类语言,稆 序 1.11的 变 K空 间需求是 Ssum(Ⅰ)=轧 um(″)=″ ,彳 楚数组长度。C语 言的参数传递方法虽然也是传值 调用,但 如呆传递的是数组参蚩,C只 传递数组第 一个元素 的首地址,并 不复制整个数组,因 而,曳 um(″)=0。 □ ftoat sum(float list [] , int n) t float tempsum = 0; int t ; for (i - 0; i< n; i++) tempsum += lisL [i] ; return tempsum; ) 例 1.8程 序 1.12 归调用保存参童、 程序 1.11数 组求和的循环实现 也是增加了一个数细~,不 过这个求和程序是递归程序,编 泽器要为每次递 局部变童、返冂地址。 f l o a t sum(fl-oat list [] , int n ) i if (n) return rsum (Iist, n-1) + list [n-1] ; return 0; ) 程序 1.12数 组求和的递归实现 本例中,一 次递归调用所需的空间是两个参蚩的字节数加上返冂地址的字节数。假定整 数和指针所需字节数都是 茌,图 1.1示 出每次递归调用所需的字节数
第1章基本概念 类别 名称字节数 参其：数组指针 11st[7 4 参量：整数 返同地址：（内部使用） 4 每次递归所需空间总和 12 图1.1序1.12每次递调用所需空间 如果数组的成员个数是H=MAX_SIZE,那么变长空间总和是Srsum(MAX_SIZE)=12× MAX SIZE。当MAX SIZE取1000时，这个递门f程序的变K空间需求为12×1000=12000 字节。比较求和程序的循环实现和递归实现，前者无变长空间需求，而后者的开销要人许 多。 ◇ 习题 1.计算S1.3习题7求解阶乘的循环函数和递归函数的空间复杂度。 2.计算s1.3习题8求解Fibonacci数列的循环函数和递归函数的空间复杂度。 3.计算13习题9求解二项式系数的循环函数和递门函数的空间复杂度。 4.计算51.3习题5函数的空间复尔度（鹤笼原理）。 5.计算$1.3习题12的数的空间复杂度（幂集问题）。 $1.52时间复杂度 程序P的时间开销记为T(P),是编译时间和运行（执行）时间的总和，舞译时间与定长 空间需求类似，同样马实例特征无关：而且，程序经检验确定其正确性之后，编译结果可不 特执行。所以时间复杂度仅考虑程序的执行时间Tp。 准确计算Tp需要详细考察编译器的工：作属性，即程序源代码到日标代码的翻译过程， 我们考虑一个简单程序，假定只做加、减运算，令n是实例特征，Tp可用下式表示： Tp(n)=ca ADD(n)+cs SUB(n)+C:LDA(n)+Cs:STA(n) 其中ADD(n),SUB(n),LDA(n),STA(n)分别是加、减、取、存操作关于实例特征n所需执 行的次数，ca,cs,cs分别对应各个操作一次执行的时间常量。 如此繁琐的估计，实在是太过份了，更好的做法是直接用系统时钟测革程序的运行时 间，后续内容留有篇幅专门介绍这种方法。现在介绍的方法，是统计程序执行时所需各操作 的次数。这种方法的计数结果与机器无关，但肖先要把程序分成独立的程序步， 定义程序步是与实例特征无关的、根据语法或语义划分的程序片段
20 第 】章 基本概念 类 别 名称 字节数 参鞋:数 细^指针 参蚩:整 数 返冂地址:(内 部使川) 1ist[] P, 4 4 4 每次递归所需空问总和 12 图1.1稆 序 1.12每 次递丿:j调川所需空问 如呆数纽i的成员个数是 彳=M眍 sIzE,那 么变K空 间总和是 孰sum(~L眍 ~SIZE)=12× MAX SIZE。 当 阻 x sIzE取 1000时 ,这 个 递 归 稆 序 的 变 K空 间 需 求 为 12× 1000=1⒛ 00 字节。比较求和稆序的循环实现和递归实现 ,前 者无变 K空 间需求 ,而 后者的开销耍人许 多。 □ 习题 1.计 算 §1.3习 题 7求 解阶乘的循环函数和递火J函数的空问复杂度。 2.计 算 §1.3习 题 8求 解 Fbonacci数 列的循环函数和递归函数的空间复杂度。 3.计 算 §1.3习 题 9求 解工项式系数的循环函数和递少l函数的空间复杂度。 4.计 算 §1.3习 题 5函 数的空间复杂度(鸽笼原理)。 5,计 算 §1.3习 题 12函 数的空间复杂度(幂集问题)。 §1.5.2 时 间复杂度 程序 P的 时问开销记为 T(P),足 编泽时间和运行 (执行)时 问的总和。编泽时问与定 K 空间需求类似,同 样与实例特征无关;而 且,稆 序经检验确定其正确性之后,编 泽结杲可不 断执行。所以时间复杂度仅考虑稆序的执行时问 %。 准确计算 %需 耍详细考察编 泽器的 l∶作属性,即 程序源代码到 日标代码的翻 泽过稆。 我们考虑一个简单稆序,假 定只做加、减运算,令 彳足实例特征,%可 用下式表示: TP(彳 )=c伢 ADD(彳 )+csSUB(″ )+C`LDA(彳 )+csF STA(彳 )、 其中 ADD(彳 )'sUB(彳 )'LDA(彳 )'STA(彳 )分 别足加、减、取、存操作关 Tˉ实例特征 彳所需执 行的次数,c伢'cs'q'csf分 别对应各个操作一次执行的时间常章。 如此繁琐的估计,实 在是太过份了,更 好的做法足直接用系统时钟测薰稆序的运行时 间,后 续内容留有篇幅专 门介绍这种方法。现在介纟亻{的方法,是 统计程序执行时所需各操作 的次数。这种方法的计数结呆与机器无关,但 首先要把稆序分成独立的稆序步。 定义 程序步足与实例特征无关的、根据语法或语义划分的稆序片段。 □
s1.5性能分析 21 注意，程序步的计算常随表示的不同而不同。例如， a=2; 是一个程序步， a 2+b 3*c/d-e f/g/a/b/ci 是另一个程序步，前者简单，所需计算时间较少，后者复杂，所需计算时间较多。两者的共 同点在于，它们都被看作一个程序步，且所需计算时间与实例特征无关。 下面我」在程序中设一个全局变量count,用米累计程序或函数的程序步，count的初 值设为0，语句插入在累加可执行语句次数的地方。 例1.9（数表求和，循环实现）本例统计求利和程序1.11的程序步个数，程序1.13给出cout 语句的位置。注意，只有可执行语句需要计数，其它如程序首部马第二句变量声明不在计数 之列。 float sum(float list(],int n) float tempsum =0:count++:/for assignment int i; for(1=0;icn:i+)【 count++;/for the for loop + tempsum +list [i];count++;/+for assignment } count++;last execution of for + count++:/t for return + retur tempsum; 程序1.13程序1.11加入count语句 由于我们的日的是获取计数值，因此，程序1.3中那些可执行语句可以去掉，这样得到 简化的程序1.14，使得计数的算术过程更加清渐。程序1.14中cout的初值是0，最后结果 是2+3，所以求和程序的程序步数日为21+3。 float sum(float list (]int n) float tempsum 0; int i; for(任=0：in;i+) coun上+=2； count+=3; return 0; 程序114程序1.13的简化
§】。5性 能分析 注意,程 序步的计算景随表示的不同而不同。例如, a = 2氵 足一个程序步, a = 2★ b + 3*c/d - e 十 f/g/a/b/C氵 足另一个稆序步,前 者简单,所 需计算时问较少,后 者复杂,所 需计算时间较多。两者的共 同点FE J1,它 们都被看作一个程序步,且 所需计算时间与实例特征无关。 下面我们在稆序中设一个全局变量 ∞unt,用 来累计稆序或函数的稆序步,∞ unt的 初 值设为 0,语 句插入在累加01执 行语句次数的地方。 例 1.9(数 表求和,循 环实现)本 例统计求和稆序 1.1a的 程序步个数,程 序 1.13给 出 ∞unt 语句的位置。注意,只 有可执行语句需要计数,其 它如稆序酋部与第工句变童声明不在计数 乏列。 float sum(float list [] , int n) t t float tempsum = 0; count++; /* for assignment */ int i; for (i = 0; i< n; i++) { count++; /* for the for loop */ tempsum += list[i]; count++; /* for assignment * / ] ) count++; /* l-ast execution of for */ count++; /* for return */ rot-1tr t-omnarlm. evrrrl/v uLrr t l ) 程 序 1.1S程 序 1.11加 入 count语 句 由 「ˉ我们的 日的足获取计数值,冈 此,稆 序 1.13中 那些可执行语句可以去掉,这 样得到 简化的程序 1.⒕,使 得计数的算术过程更加清晰。程序 1.1在中 ∞unt的 初值是 0,最 后结果 足 2″+3,所 以求和程序的程序步数 冂为 ⒛ +3。 □ fl-oat sum(float list [] , int n) t fIoat, tempsum = 0; int i; for (i - 0; i < n,' i++) count += 2; count += 3; return 0; ) 21 程序 1.14程 序 1.13的 简化
3 第1章基本概念 例1.10（数表求和，递归实现）本例统计数表求和递归程序的程序步数日。程序1.15在原米 的程序1.12加入count语句。 float rsum(float list[],int n) count++;/*for if conditoinal+/ if (n)( count++;/.for return and rsum invocation+/ reutrn rsum(list,n-1)+list [n-1]; count++; return list [0]; 程序1.15程序1.12加入count语句 我们先确定n=0时的边界条件，在程序1.15中，当n=0,只有1条件语句和第二条 return语句执行，因此程序步为2。当n>0,i:条件语句和第一条return语句执行，因 此，当n>0,每次递归调用为计数贡献2。最，由于共有n次递归调州，加上n=0的 次，这个程序的程序步总数是2n+2。 这个递山程序的程序步比相应循环程序的程序步少，初看令人惊奇，但不要忘记，程序 步的计数仅告诉我们程序以多少程序步执行，并未告诉我每一程序步的执行时间。实际 上，递归程序的执行，一般而言，要比循环程序慢，递归程序显然程序步少于循环程序， 花的时间却要多一些。 ◇ 例111（矩阵加法）程序1.16是两维数组求和，我们要统计这个程序的程疗步数日。数组。 和数组b相加，结果存入数组c,每个数组的维数都是xows×row8。程序1.17在add函数 中加入程序步计数。和上面儿个例了一样，程序步计数同样是关丁输入量的长度，本例中是 xows和co1s。为了让程序更易读，我们把同一个循环体中的cout语句合在一起，给出了 形式更简单的程序1.18。 在程序1.18中，count的初值是0，最后结果是2xow8·co1a+2rows+1。根据这个结 果，如果矩阵的行数比列数人很多，那么应把矩阵转置。 ▣ void add(int a[][MAX_SIZE],int b[][MAX_SIZE] int c[][MAX_SIZE],int rows,int cols) int i,j; for (i=0;icrows;i++) for (j-0;j<cols;j++) c[][]=ati][]+b(][] 程序1.16矩阵加法
22 例 1.10(数 表求和,递 归实现)本 例统计数表求和递归稆序的程序步数 日。 的 程 序 1.12加 入 ∞ unt语 句 。 第 】章 基本概念 程序 1.15在 原来 fLoat rsum(fLoat list [] , int n ) t count++; /*for if conditoinal- */ if (n) t count++; /* for return and rsum invocation */ reutrn rsum(Iist, n-1) + Iist[n-1]; ) count++,' return list [0] ; ) 程 序 1.15程 序 1.12加 入 Courlt语 句 我们先确定 刀=0时 的边界条件,在 程序 1.15中 ,当 ″=0,只 有 土￡条件语句和第工条 retum语 句执行,冈 此程序步为 2。 当 ″)0,土 f条 件语句和第一条 retum语 句执行,冈 此,当 彳)0,每 次递归调用为计数贡献 2。最后,由 Tˉ共有 彳次递归调用,加 上 ″=0的 一 次,这 个程序的程序步总数是 2彳+2。 这个递归程序的程序步比相应循环程序的稆序步少,初 看令人惊奇,但 不要忘记,程 序 步的计数仅告诉我们不V序 以多少程序步执行,并 木告诉我们每一稆序步的执行时间。实际 上,递 丿l稆序的执行,一 般而言,耍 比循环程序慢,递 归稆序虽然程序步少 Tˉ循环程序,但 花的时间却要多一些。 □ 例 1.11(矩 阵加法)稆 序 1.16是 两维数组求和,我 们耍统计这个程序的稆序步数 日。数细~a 和数组 b相 加,结 呆存入数组 c,每 个数组的维数都是 r。ws× r。ws。 稆序 1.17在 add函 数 中加入程序步计数。和上面儿个例 r一 样,稆 序步计数同样足关 T输 入甘的κ度,本 例中是 rows和 ∞1s。 为了让稆序更易读,我 们把同一个循环体中的 count语 句合在 一起,给 出了 形式更简 单的程序 1.18。 在稆序 1.18中 ,count的 初值是 0,最 后结呆是 2r。ws· ∞1s+zrows+1。 根据这个结 呆,如 杲矩阵的行数比列数人很多,那 么应把矩阵转置。 □ vo土 d add(土 n△ a[] [MAX SIZE]` 土 nt b[] [MAX SIZΞ ]` 土nt c[] [MAX SIZE]` 土 nt rows` 土 nt co1s) ( 土n△ 土 ` 彐 ` ￡or (土 =0` 土 (rOws` 土 ++) ￡or (j〓 0` j<co1s氵 」 ++) c[土 ][j] = a[土 ][j] + b[土 ][j]` 程序 1.16矩 阵加法
51.5性能分析 23 void add(int a[][MAX_SIZE],int b[][MAX_SIZE], 1ntgI1[MAX SIZE】,1 nt rowg,int co1g】 int i,j for (i=0;icrows;i++){ count++i/+for i for loop/ for (j-0;j<cols;j++)( count++;/for j for loop/ a「i1[h1=a[i】[i】+b[i1[i】: count++;/+for assignment statement+/ 1 count++:/.last time of j for loop * count++i/.last time of i for loop./ 程序1.17矩阵加法加入count语句 void add(int a[][MAX_SIZE],int b[][MAX_SIZE], int c[][MAX_SIZE],int rows,int cols) int i,ji for(i=0;1crow8;1++】 for (j=0;j<cols;j++) count +=2; count+=2; count++i 程序1.18程序1.17的简化 上面给出的例子，我们把cout语句嵌入函数之中，这样的好处是，实际运行以上程序， 能得到关于各种实例特征的程序步数日。卜面我们介表方法，同样可以获得程序步数目， 这种方法称为“程序步/执行”(stps/execution),或简称为s/e。接卜米，我们用这种方法找 出每条语句的程序步计数，这个计数称为频率。不可执行语句的频率是0，把s/与率相 乘，得到每条语句的程序步计数，把何条语句的程序步计数加起米，结果就是整个函数的程 序步计数。乍-一看，这种做法挺林烦，其实并非如此。我们用表方法重做上面三个例子。 例1.12（数表求和，循环实现）图1.2是程序1.11的程序步计数表。造表的过程是这样的。 片先填写每条语句的s/e栏，然后填频率栏。第5行的or循环语句略复杂些，由于从0开 始，i在等于n时结来，所以频率是n+1,而第6行的循环体语句只执行n次，1=n时不执 行。得到每条语句的程序步个数之后，整个函数的程序步数日就是它们的总和
§】.5性 能分析 23 vo土 d add(土 nt a[] [MAX SIZE]` 土 nt b[] [MAX SIZE]` 土n△ c[] [MAX SIZE]` 土 nt rows` 土 nt co1s) ( 土n△ 土 ` ]F ￡or (土 =Of 土 (rows` i++) ( coun△ ++` /★ for 立 for Ι oop ★ / f° r (」 〓 0氵 j(C01s氵 j++) ( count++氵 /★ fOr J for Ι oop */ c[土 ][j] 〓 a[i][j] + b[土 ][j]氵 count++` /★ for ass立 gnment sε aε emenε ★ / ) coun乜 十 十 氵 /★ Ⅰ aSε t立 me of J f。 r Ι 。 op ★ / ) count++` /★ Ⅰ ast ε 立 me of 立 for Ι OOp ★ / ) 程 序 1.17矢 巨阵 加 法 加 入 cOunt语 句 vo土 d add(土 nt a[] [MAX_sIZE]` 土 n△ b[] [MAX~sIzE]` 土nt c【 ] [MAX SIzE]` 土 nt rows` 土 n△ co1s) ( 土nt 主 ` 彐 ` ￡or (土 =0` 土 (rows氵 土 ++) ( ￡or (j=0` j(c01s` j++) c⊙ unt +=2' coun乜 +=2` ) count++'。 ) 程 序 1.18程 序 1.17的 简 化 上面给出的例子,我 们把 count语 句嵌入函数乏中,这 样的好处楚,实 际运行以上程序, 能得到关于各种实例特征的程序步数 日。 卜面我们介纟亻i表方法,同 样可以获得程序步数 目, 这种方法称为 “程序步/+t行 ”otps/execution),或 简称为 s/e。 接下来,我 们用这种方法找 出每条语句的程序步计数,这 个计数称为频率。不可执行语句的频率足 0,把 s/e与 频率相 乘,得 到每条语句的稆序步计数,把 每条语句的程序步计数加起来,结 果就是整个函数的程 序步计数。乍 一看,这 种做法挺麻烦,其 实并非如此。我们用表方法重做上面二个例子。 例 1。⒓ (数表求和,循 环实现)图 1.2是 不V序 1.11的 程序步计数表。造表的过程是这样的。 首先填写每条语句的 s/e栏 ,然 后填频率栏。第 5行 的 ￡or循 环语句略复杂些,由 Tˉ从 0开 始,i在 等Tˉn时 结束,所 以频率是 彳+1,而 第 6行 的循环体语句只执行 ″次,土=〓n时 不执 行。得到每条语句的程序步个数之后,整 个函数的程序步数 目就足它们的总和。 □