是多大,所以,不论使用引用参数还是使用传值参数,都有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)