第二章算法与分析

1、1. 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5)(4) h(n)=O(nlgn) 2. 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0;while(in)k=k+10*i;i+; (2) i=0; k=0;dok=k+10*i; i+; while(in); (3) i=1; j=0; while(i+jj) j+;else i+

2、; (4) x=n; / n1 while (x=(y+1)*(y+1) y+; (5) x=91; y=100; while(y0) if(x100) x=x-10;y-;else x+; 3. 算法的时间复杂度仅与问题的规模相关吗?4. 按增长率由小至大的顺序排列下列各函数：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2)5. 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大O记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n

3、=2.0lgn+O(n),这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?答案:1.设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立：(1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5)(4) h(n)=O(nlgn)分析：数学符号O的严格的数学定义：若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n）表示存

4、在正的常数C和n0，使得当nn0时都满足0T（n）Cf（n）。通俗地说，就是当n时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即：O(f(n)=n3O(g(n)=n3O(h(n)=n1.5所以答案为：答：（1）成立。 （2）成立。（3）成立。（4）不成立。2. 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0; while(in) k=k+10*i;i+; 分析：i=1; /1k=0; /1while(in) /n k=k+10*i; /n-1i+; /n-1 由以上列出的各语句的频度，可得该程序

5、段的时间消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)=O(n)(2) i=0; k=0;dok=k+10*i; i+; while(in); 分析：i=0; /1k=0; /1do /nk=k+10*i; /ni+; /nwhile(in);/n 由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2可表示为T(n)=O(n)(3) i=1; j=0; while(i+jj) j+;else i+;分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while

6、循环，而while循环共做了n次，所以该程序段的执行时间为：T(n)=O(n)(4) x=n; / n1 while (x=(y+1)*(y+1)y+;分析：由x=n且x的值在程序中不变，又while的循环条件(x=(y+1)*(y+1)可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)n得：y0)if(x100)x=x-10;y-;else x+;分析：x=91; /1y=100; /1while(y0) /1101if(x100) /1100x=x-10; /100y-; /100else x+; /1000以上程序段右侧列出了执行次数。该程序段的执行时间为：T

7、(n)=O(1)3.算法的时间复杂度仅与问题的规模相关吗?答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。4.按增长率由小至大的顺序排列下列各函数：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)、

8、指数阶0(2n)。先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n(3/2)指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn、(2/3)n注意：(2/3)n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n 2100 lgn n0.5 n(3/2) nlgn (3/2)n 2n n! nn 5.有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大O记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣? 函数大O表示优劣 (1) T1(n)=5n2