2014/4/7 例1：素数的判断算法。 例2：冒泡排序法。 Void prime(intn)/*n是一个正整数*/ Void bubble sort(int all,int n) int i=2; for (i=n-1,change=TURE;i>1 &change;-i) while ((n%i)!=0 &&i*1.0<sgrt(n))++; if(i*1.0>sgrt(n)） change=false: printf(“&d是一个素数n”,n); for (j=0;j<i;++i) else if (aljl>alj+1D) printf(“&d不是一个赛数n”,n); {all←-一→ajt1;change=--TURE;} 嵌套的最深层语句是计+；其频度由条件(% ◆最好情况：0次 =0&&i*1.0sqrt(o)决定，显然i*1.0<sqrt(a),时 令最坏情况：1+2+3++n-1=n(n-1)/2 间复杂度0(m2)。 平均时间复杂度为：0(m) 81.2算法描述与分析 作业 ■空间复杂度(Space complexity):是指算法编写成程 1数据的逻辑结构？数据的物理结构？逻辑结构与物 序后，在计算机中运行时所需存储空间大小的度量。 记作：S(=O(f)其中：n为问题的规模（或大小） 理结构的区别和联系是什么？ 该存储空间一般包括三个方面： 2分析以下程序段的时间复杂度，请说明分析的理由 或原因。 ◆指令常数变量所占用的存储空间： (1) ·输入数据所占用的存储空间： suml(intn） ◆辅助（存储）空间。 int p=1,sum-0,m for (m-1;m<-n;m++) 一般地，算法的空间复杂度指的是辅助空间。 {p*-m;sum+=p;】 。一维数组a:空间复杂度O(m return (sum); 二维数组a口m:空间复杂度O和*m) (2) Sum2(int n) 3.按增长率由小至大的顺序排列下列各函数： int sum-0,m,t; 2o0,(3/2°，(23y,n,,nl,2,lgn,n,n for (m-l;m<-n;m++) {p-l; for (t=l;t<-m;t++)p*-t; 4.有时为了比较两个同数量级算法的优劣，须突出主项 sum+-p 的常数因子，而将降低次项用大“口”记号表示。例如 return (sum); 设T,(n=1.39 nign+100n+256=1.39nlgn+0(n),T(n) =2.0nlgn-2n=2.0nlgn+0(n),这两个式子表示，当n 足够大时r,(n)优于T),因为前者的常数因子小于后 (3)递归函数 者。请用此方法表示下列函数，并指出当足够大时， fact(int n) 哪一个较优，哪一个较劣？ if (n<-1)return(1) (1)T,(n=5n2.3n+60lgn2)T2(n=3n2+1000n+3lgn else return(n*fact(n-1)); (3)T3n=8n2+31gn (4T,(nj=1.5n2+6000nlgn 72014/4/7 7 例1：素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\n” , n) ; 37 else printf(“&d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.0< sqrt(n) ) 决定，显然i*1.0< sqrt(n) ，时 间复杂度O(n1/2)。 例2：冒泡排序法。 Void bubble_sort(int a[]，int n) { for (i=n-1, change=TURE; i>1 && change; --i) change=false; for (j=0; j<i; ++j) if (a[j]>a[j+1]) 38 if (a[j]>a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } }  最好情况：0次  最坏情况：1+2+3+⋯+n-1=n(n-1)/2  平均时间复杂度为： O(n2) 空间复杂度(Space complexity) ：是指算法编写成程 序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面：  指令常数变量所占用的存储空间; §1.2 算法描述与分析 39  指令常数变量所占用的存储空间;  输入数据所占用的存储空间;  辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。  一维数组a[n]： 空间复杂度 O(n)  二维数组a[n][m]： 空间复杂度 O(n*m) 作 业 1 数据的逻辑结构？数据的物理结构？逻辑结构与物 理结构的区别和联系是什么？ 2 分析以下程序段的时间复杂度，请说明分析的理由 或原因。 40 ⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; } ⑵ Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++) { p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; 41 return (sum) ; } ⑶ 递归函数 fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; } 3. 按增长率由小至大的顺序排列下列各函数： 4. 有时为了比较两个同数量级算法的优劣，须突出主项 的常数因子，而将降低次项用大“O”记号表示。例如， 设 T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n) ， T2(n) 100 n n n n lgn 3/2 2 , (3/2) , (2/3) , n , n, n!, 2 , lgn, n , n 42 1 2 = 2.0nlgn-2n=2.0nlgn+O(n)，这两个式子表示，当n 足够大时T1(n)优于T2(n)，因为前者的常数因子小于后 者。请用此方法表示下列函数，并指出当n足够大时， 哪一个较优，哪一个较劣？ ⑴ T1(n)=5n2-3n+60lgn ⑵ T2(n)=3n2+1000n+3lgn ⑶ T3(n)=8n2+3lgn ⑷ T4(n)=1.5n2+6000nlgn