复杂度分析练习题 | 王争《数据结构与算法之美》 -极客时间


时间复杂度练习题

练习题一: 

求以下算法的时间复杂度

sum=0;
for(i=1;i<=n;i++) 
    for(j=1;j<=n;j++)
        sum++;

练习题二:

求以下算法的时间复杂度

for (i=1;i<n;i++)  {
    y=y+1;
    for (j=0;j<=(2*n);j++)
        x++;
}

练习题三:

求以下算法的时间复杂度

a=0;
b=1;   
for (i=1;i<=n;i++)   {
    s=a+b;
    b=a;
    a=s;
} 

练习题四:

 for (i=1; i<=n; i+=2) ; 的时间复杂度为-----
 A: O(n)  B: O(log2n)   C: O(n2) D: O(n3)

练习题五:

求以下算法的时间复杂度

i=1;
while (i<=n)
    i=i*2;

练习题六:

求以下算法的时间复杂度

for(i=1;i<=n;i++)  {
    for(j=1;j<=i;j++)  {
        for(k=1;k<=j;k++)
            x=x+2;
    }
}

练习题七:

某算法的时间复杂度为O(n2),表明该算法的( )
A.问题规模是n2 B.执行时间等于n2
C.执行时间与n2成正比 D.问题规模与n2成正比

练习题八:

设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()

x=2;
while(x<n/2)
    x=2*x;

练习题九:

求整数n (n>=0)阶乘的算法如下,其时间复杂度是( )

int fact(int n){
    if (n<=1) return 1;
    return n*fact(n-1);
}

练习题十

程序段

for(i=n-1;i>1;i--)
   for(j=1;j<i;j++)
       if (A[j]>A[j+1])
           A[j]与 A[j+1]对换;

其中n为正整数,则最后一行的语句频度在最坏情况下是( )

练习题十一

下面说法错误的是( )。
Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间
Ⅱ.在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
Ⅲ.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
Ⅳ.同一个算法,实现语言的级别越高,执行效率就越低

A. Ⅰ B. Ⅰ、Ⅱ C. Ⅰ、Ⅳ D. Ⅲ

练习题十二

分析以下各程序段,求出算法的时间复杂度。

// 程序段①
i=1;k=0;
while(i<n-1){
    k=k+10*i;
    i++;
}
// 程序段②
y=0;
while((y+1)*(y+1)<=n)
    y=y+1;
// 程序段③
for(i=1;i<=n;i++)
    for(j =1;j <=i;j ++)
        for(k=1;k<=j;k++)
            x++;
// 程序段④
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i] [j]=0;

答案

练习题一

sum=0; # (1次)
for(i=1;i<=n;i++) 
    # (n次)
    for(j=1;j<=n;j++)
        #(n2次)
        sum++; # (n2次)

解:T(n) = 2n2+n+1 = O(n2)

练习题二

for (i=1;i<n;i++)  {
    y=y+1; # ①
    for (j=0;j<=(2*n);j++)
        x++; # ②
}

解:语句1的频度是n-1
语句2的频度是(n-1)(2n+1)=2n2-n-1
f(n)=2n2-n-1+(n-1)=2n2-2
该程序的时间复杂度T(n) = O(n2)

练习题三

a=0;
b=1;   # ①
for (i=1;i<=n;i++)   {
    # ②
    s=a+b; # ③
    b=a; # ④
    a=s; # ⑤
} 

解:语句1的频度:1,
语句2的频度:n,
语句3的频度:n-1,
语句4的频度:n-1,
语句5的频度:n-1,
T(n) = 1+n+3(n-1) = 4n-2 = O(n)

练习题四

for(i=1; i=n; i+=2); 的时间复杂度为 A. O(n)

练习题五

i=1; # ①
while (i<=n)
    # ②
    i=i*2;

解:语句1的频度是1
设语句2的频度是f(n),
则:2^f(n)=n; f(n)=log2n
取最大值f(n)=log2n, T(n)=O(log2n)

练习题六

for(i=1;i<=n;i++)  {
    for(j=1;j<=i;j++)  {
        for(k=1;k<=j;k++)
            x=x+2;
    }
}

解:循环共进行了1+(1+2)+(1+2+3)+…+(1+2+3+…+n) = n(n+1)(n+2)/6 次,
所以,时间复杂度为T(n) = O(n^3)
这个题复杂一点,关于上面等式的计算,参考 求解Sn=1+1+2+1+2+3+1+2+3+4+.+n的和-作业帮

练习题七:

某算法的时间复杂度为O(n2),表明该算法的( )
A.问题规模是n2 B.执行时间等于n2
C.执行时间与n2成正比 D.问题规模与n2成正比
此题选C,时间复杂度为O(n2),说明算法的执行时间T(n)<=c * n2(c为比例常数),即T(n)=O(n2),时间复杂度T(n)是问题规模n的函数,其问题规模仍然是n而不是n2。

练习题八:

设n是描述问题规模的非负整数,下面程序片段的时间复杂度是()

x=2;
while(x<n/2)
  x=2*x;

T(n)=O(log2n),在程序中,执行频率最高的语句为“x=2*x”。设该语句共执行了 t次,则2t+1=n/2,故t=log2(n/2)-1=log2n-2,得 T(n)=O(log2n)。

练习题九:

求整数n (n>=0)阶乘的算法如下,其时间复杂度是( )

int fact(int n){
    if (n<=1) return 1;
    return n*fact(n-1);
}

T(n)=O(n),本题是求阶乘n!的递归代码,即n(n-1)...*1共执行n次乘法操作,故T(n)=O(n)。

练习题十:

程序段

for(i=n-1;i>1;i--)
   for(j=1;j<i;j++)
       if (A[j]>A[j+1])
           A[j]与 A[j+1]对换;

其中n为正整数,则最后一行的语句频度在最坏情况下是( )
T(n)=O(n2),当所有相邻元素都为逆序时,则最后一行的语句每次都会执行。此时

所以在最坏情况下的该语句频度是O(n2)。

练习题十一

下面说法错误的是( )。
Ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间
Ⅱ.在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
Ⅲ.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
Ⅳ.同一个算法,实现语言的级别越高,执行效率就越低

A. Ⅰ B. Ⅰ、Ⅱ C. Ⅰ、Ⅳ D. Ⅲ
此题选A
Ⅰ,算法原地工作是指算法所需的辅助空间是常量。Ⅱ,题中是指算法的时间复杂度,不要想当然认为是程序(该算法的实现)的具体执行时间,而赋予n—个特殊的值。时间复杂度为O(n)的算法,必然总是优于时间复杂度为O(2n)的算法。Ⅲ,时间复杂度总是考虑在最坏情况下的时间复杂度,以保证算法的运行时间不会比它更长。Ⅳ为严蔚敏教材的原话。

练习题十二

分析以下各程序段,求出算法的时间复杂度。

// 程序段①
i=1;k=0;
while(i<n-1){
    k=k+10*i;
    i++;
}
// 程序段②
y=0;
while((y+1)*(y+1)<=n)
    y=y+1;
// 程序段③
for(i=l;i<=n;i++)
    for(j =1;j <=i;j ++)
        for(k=l;k<=j;k++)
            x++;
// 程序段④
for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i] [j]=0;

①基本语句是k=k+10i,共执行了n-2次,所以T(n) = O(n)。
②设循环体共执行T(n)次,每循环一次,循环变量y加1,最终T(n)=y。故(T(n))2<=n,解得 T(n) = O(n1/2)。
③参考练习题六,T(n) = O(n3)
④ai=0是基本语句,内循环执行m次,外循环执行n次,共执行了mn次,所以 T(m, n) = O(mn)

本文发表于2018年09月29日 15:52
阅读 2325 讨论 1 喜欢 5

日韩化妆品代购 正品保证 假一赔十

刀架在脖子上让发的,走过路过看一下8....

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

7008 2392372
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

考985不牛逼,考上才牛逼。创业不牛逼,创业成功才牛逼。这个社会上很多人把目标当成牛逼的资本,牛逼哄哄的,死活不听劝,然后做的一塌糊涂,给别人添麻烦,让别人帮他料理后事,对此只能呵呵。

当你尝到用生气解决问题的甜头后,你就懒得再用其他方式了。你却忽略了,生气是鸩毒啊,剂量用够了,你的关系也玩完了。

年轻的时候你只搞事业不谈恋爱,等你事业有成了,钱相对自由了,你可能已经没有荷尔蒙了。

如果你经常雇佣比你矮小的人,将来我们就会变成矮人国,变成一家侏儒公司。相反,如果你每次都雇用比你高大的人,日后我们必能成为一家巨人公司。

如果一个人有充裕的时间去完成一项工作,那么他就会放慢节奏或者增加其他不必要的工作,直到花光所有的时间。

天空不是人类休息的地方,人类应该去亲近海洋。

一个人的正直程度,取决于他肯为原则付出的牺牲。

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.