数据结构与算法材料第一章绪论习题1.pptx

习题1 设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0;  　　while(in) 　　　{ k=k+10*i;i++; 　　　}  解析： 　　i=1; //1 　　k=0; //1 　  while(in) //n 　　　{ k=k+10*i; //n-1 　　　　i++; //n-1 　　　}  由以上列出的各语句的频度，可得该程序段的时间消耗： 　　　T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n) (2) i=0; k=0; 　　do{ 　　　　k=k+10*i; i++;  　　　} 　　while(in);  解析： 　　i=0; //1 　　k=0; //1 　　do{ //n 　　　　k=k+10*i; //n 　　　　i++; //n 　　　} 　　while(in);//n  由以上列出的各语句的频度，可得该程序段的时间消耗： 　　T(n)=1+1+n+n+n+n=4n+2 可表示为T(n)=O(n) (3) i=1; j=0;  　　while(i+j=n)  　　　{ 　　　　if (ij) j++; 　　　　else i++; 　　　}  解析： 　　通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： 　　　　T(n)=O(n) (4) x=91; y=100;      while(y0) 　　　　if(x100) 　　　　　{x=x-10;y--;} 　　　　else x++; 解析： 　　x=91; //1 　　y=100; //1 　　while(y0) //1101 　　　　if(x100) //1100　　　　　{　x=x-10; //100 　　　　　　y--; //100 　　　　　} 　　　　else  　　　　　x++; //1000 　　以上程序段右侧列出了执行次数。该程序段的执行时间为：　　　　　　T(n)=O(1) 三. 按增长率由小至大的顺序排列下列各函数： 　　 　2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 常数阶0(1) 对数阶0(log2n) 线性阶0(n) 线性对数0(nlog2n) 平方阶0(n2) 立方阶0(n3) k次方阶0(nk)(k3) 指数阶0(2n) 常数阶0(1): 对数阶0(log2n): lgn 线性阶0(n): 线性对数0(nlog2n): 平方阶0(n2): 立方阶0(n3): k次方阶0(nk): n0.5、n(3/2) 、nlgn 指数阶0(2n): (3/2)n、2n、 n!、 nn (2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 三. 按增长率由小至大的顺序排列下列各函数： 　　 　2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) (2/3)n 2100 lgn n0.5 n(3/2) nlgn (3/2)n 2n n! nn