1.2 算法和算法评价·习题

教材导航 · 返回本节知识

复习入口

1.2 算法和算法评价 · 1.2.1 算法的基本概念 · 1.2.2 算法效率的度量

本节共18题:选择题17题,综合应用题1题。每题答案紧接题目折叠显示。

文字转录进度:18/18题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P6 · 解析P8 · 目视转录

一个算法应该具有( )等重要特性。

A. 可维护性、可读性和可行性

B. 可行性、确定性和有穷性

C. 确定性、有穷性和可靠性

D. 可读性、正确性和可行性

查看答案与解析

答案:B。

一个算法应具有五个重要特性:有穷性、确定性、可行性、输入和输出。选项 A、C 和 D 中提到的特性(如可维护性、可读性、可靠性、正确性等)是很重要的,但它们并不是算法定义的重要特性,更多的是关于软件开发中的附加要求。

单项选择题 02

原书题目P6 · 解析P8 · 目视转录

下列关于算法的说法中,正确的是( )。

A. 算法的时间效率取决于算法执行所花的 CPU 时间

B. 在算法设计中不允许用牺牲空间效率的方式来换取好的时间效率

C. 算法必须具有有穷性、确定性等五个特性

D. 通常用时间效率和空间效率来衡量算法的优劣

查看答案与解析

答案:C。

算法的时间效率是指算法的时间复杂度,即执行算法所需的计算工作量,选项 A 错误。算法设计会综合考虑时间效率和空间效率两个方面,若某些应用场景对时间效率要求很高,而对空间效率要求不高,则可用牺牲空间效率的方式来换取好的时间效率,选项 B 错误。评价一个算法的“优劣”不仅要考虑算法的时空效率,还要从正确性、可读性、健壮性等方面来综合评价。

单项选择题 03

原书题目P6 · 解析P8 · 目视转录

某算法的时间复杂度为 O(n2)O(n^2),则表示该算法的( )。

A. 问题规模是 n2n^2

B. 执行时间等于 n2n^2

C. 执行时间与 n2n^2 成正比

D. 问题规模与 n2n^2 成正比

查看答案与解析

整理注记

本题按教材对增长阶的常见表述选择答案。严格说,O(n²)只给出渐近上界,不能单凭它推出运行时间必与n²成正比;紧确阶应使用Θ(n²)。

原书答案:C。

时间复杂度为 O(n2)O(n^2),说明算法的时间复杂度 T(n)T(n) 满足 T(n)≤cn2T(n)\le cn^2(其中 cc 为比例常数),即 T(n)=O(n2)T(n)=O(n^2)。时间复杂度 T(n)T(n) 是问题规模 nn 的函数,其问题规模仍然是 nn 而不是 n2n^2。

单项选择题 04

原书题目P6 · 解析P9 · 目视转录

若某算法的空间复杂度为 O(1)O(1),则表示该算法( )。

A. 不需要任何辅助空间

B. 所需辅助空间大小与问题规模 nn 无关

C. 不需要任何空间

D. 所需空间大小与问题规模 nn 无关

查看答案与解析

答案:B。

算法的空间复杂度为 O(1)O(1),表示执行该算法所需的辅助空间大小相比输入数据的规模来说是一个常量,而不表示该算法执行时不需要任何空间或辅助空间。

单项选择题 05

原书题目P6 · 解析P9 · 目视转录

下列关于时间复杂度的函数中,时间复杂度最小的是( )。

A. T1(n)=nlog⁡2n+5000nT_1(n)=n\log_2 n+5000n

B. T2(n)=n2−8000nT_2(n)=n^2-8000n

C. T3(n)=nlog⁡2n−6000nT_3(n)=n\log_2 n-6000n

D. T4(n)=20000log⁡2nT_4(n)=20000\log_2 n

查看答案与解析

答案:D。

A 的最高阶是 nlog⁡2nn\log_2 n,时间复杂度是 O(nlog⁡2n)O(n\log_2 n)。B 的最高阶是 n2n^2,时间复杂度是 O(n2)O(n^2)。C 的最高阶是 nlog⁡2nn\log_2 n,时间复杂度是 O(nlog⁡2n)O(n\log_2 n)。D 的最高阶是 log⁡2n\log_2 n,时间复杂度是 O(log⁡2n)O(\log_2 n)。

单项选择题 06

原书题目P6 · 解析P9 · 目视转录

下列算法的时间复杂度为( )。

void fun(int n){
    int i=1;
    while(i<=n)
        i=i*2;
}

A. O(n)O(n)

B. O(n2)O(n^2)

C. O(nlog⁡2n)O(n\log_2 n)

D. O(log⁡2n)O(\log_2 n)

查看答案与解析

答案:D。

找出基本运算 i=i*2,设执行次数为 tt,2t≤n2^t\le n,即 t≤log⁡2nt\le\log_2 n,故时间复杂度 T(n)=O(log⁡2n)T(n)=O(\log_2 n)。

更直观的方法:计算基本运算 i=i*2 的执行次数(每执行一次 ii 乘以 2),其中判断条件可理解为 2t=n2^t=n,即 t=log⁡2nt=\log_2 n,则 T(n)=O(log⁡2n)T(n)=O(\log_2 n)。

单项选择题 07

原书题目P6 · 解析P9 · 目视转录

下列算法的时间复杂度为( )。

void fun(int n){
    int i=0;
    while(i*i*i<=n)
        i++;
}

A. O(n)O(n)

B. O(nlog⁡2n)O(n\log_2 n)

C. O(n3)O(\sqrt[3]{n})

D. O(n)O(\sqrt n)

查看答案与解析

答案:C。

基本运算为 i++,设执行次数为 tt,有 t×t×t≤nt\times t\times t\le n,即 t3≤nt^3\le n。因此有 t≤n3t\le\sqrt[3]n,则 T(n)=O(n3)T(n)=O(\sqrt[3]n)。

单项选择题 08

原书题目P7 · 解析P9 · 目视转录

某个程序段如下:

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

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

A. O(n)O(n)

B. O(nlog⁡2n)O(n\log_2 n)

C. O(n3)O(n^3)

D. O(n2)O(n^2)

查看答案与解析

答案:D。

这是冒泡排序的算法代码,考查最坏情况下的元素交换次数(若觉得理解起来有困难,则可在学完第 8 章后再回顾)。当所有相邻元素都为逆序时,则最后一行的语句每次都会执行。此时,

T(n)=∑i=2n−1∑j=1i−11=∑i=2n−1(i−1)=(n−2)(n−1)2=O(n2).T(n)=\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}1=\sum_{i=2}^{n-1}(i-1)=\frac{(n-2)(n-1)}2=O(n^2).

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

单项选择题 09

原书题目P7 · 解析P9 · 目视转录

下列程序段的时间复杂度为( )。

if(n>=0){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            printf("输入数据大于或等于零\n")
}
else{
    for(int j=0;j<n;j++)
        printf("输入数据小于零\n")
}

A. O(n2)O(n^2)

B. O(n)O(n)

C. O(1)O(1)

D. O(nlog⁡2n)O(n\log_2 n)

查看答案与解析

答案:A。

当程序段中有条件判断语句时,取分支路径上的最大时间复杂度。

单项选择题 10

原书题目P7 · 解析P9 · 目视转录

下列算法中加下画线的语句 m++ 的执行次数为( )。

int m=0,i,j;
for(i=1;i<=n;i++)
    for(j=1;j<=2*i;j++)
        m++;

A. n(n+1)n(n+1)

B. nn

C. n+1n+1

D. n2n^2

查看答案与解析

答案:A。

m++ 语句的执行次数为

∑i=1n∑j=12i1=∑i=1n2i=2∑i=1ni=n(n+1).\sum_{i=1}^{n}\sum_{j=1}^{2i}1=\sum_{i=1}^{n}2i=2\sum_{i=1}^{n}i=n(n+1).

单项选择题 11

原书题目P7 · 解析P9 · 目视转录

下列函数代码的时间复杂度是( )。

int Func(int n){
    if(n==1) return 1;
    else return 2*Func(n/2)+n;
}

A. O(n)O(n)

B. O(nlog⁡2n)O(n\log_2 n)

C. O(log⁡2n)O(\log_2 n)

D. O(n2)O(n^2)

查看答案与解析

答案:C。

本题求的是递归调用的时间复杂度,递归调用可视为多重循环,每次递归执行的基本语句是 if(n==1) return 1;,因此可认为单层循环的执行次数为 1。设递归次数为 tt,2t≤n2^t\le n,即 t≤log⁡2nt\le\log_2 n,共执行了 log⁡2n\log_2 n 次递归调用,总执行次数 T=log⁡2n×1T=\log_2 n\times1,所以时间复杂度为 O(log⁡2n)O(\log_2 n)。

循环变量单层循环语句单层循环执行次数
nnif(n==1) return 1;1
n/2n/2if(n==1) return 1;1
n/4n/4if(n==1) return 1;1
⋯\cdots⋯\cdots⋯\cdots
1if(n==1) return 1;1

单项选择题 12

原书题目P7 · 解析P9 · 目视转录

【2011 统考真题】设 nn 是描述问题规模的非负整数,下列程序段的时间复杂度是( )。

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

A. O(log⁡2n)O(\log_2 n)

B. O(n)O(n)

C. O(nlog⁡2n)O(n\log_2 n)

D. O(n2)O(n^2)

查看答案与解析

答案:A。

基本运算(执行频率最高的语句)为 x=2*x,每执行一次,xx 乘以 2。设执行次数为 tt,则有 2t+1<n/22^{t+1}<n/2,所以 t<log⁡2(n/2)−1=log⁡2n−2t<\log_2(n/2)-1=\log_2 n-2,得 T(n)=O(log⁡2n)T(n)=O(\log_2 n)。

单项选择题 13

原书题目P7 · 解析P9 · 目视转录

【2012 统考真题】求整数 nn(n≥0n\ge0)的阶乘的算法如下,其时间复杂度是( )。

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

A. O(log⁡2n)O(\log_2 n)

B. O(n)O(n)

C. O(nlog⁡2n)O(n\log_2 n)

D. O(n2)O(n^2)

查看答案与解析

答案:B。

本题求的是递归调用的时间复杂度。递归调用可视为多重循环,每次递归执行的基本语句是 if(n<=1) return 1;,因此可以认为单层循环的执行次数为 1。共执行了 nn 次递归调用,总执行次数 T=1+1+⋯+1=nT=1+1+\cdots+1=n,所以时间复杂度为 O(n)O(n)。

循环变量单层循环语句单层循环执行次数
nnif(n<=1) return 1;1
n−1n-1if(n<=1) return 1;1
n−2n-2if(n<=1) return 1;1
⋯\cdots⋯\cdots⋯\cdots
1if(n<=1) return 1;1

单项选择题 14

原书题目P7 · 解析P10 · 目视转录

【2014 统考真题】下列程序段的时间复杂度是( )。

count=0;
for(k=1;k<=n;k*=2)
    for(j=1;j<=n;j++)
        count++;

A. O(log⁡2n)O(\log_2 n)

B. O(n)O(n)

C. O(nlog⁡2n)O(n\log_2 n)

D. O(n2)O(n^2)

查看答案与解析

答案:C。

对于单层循环如 for(j=1;j<=n;j++) count++;,可以直接数出执行次数为 nn,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下(假设 tt 为循环变量的幂次):

循环变量 kk单层循环语句单层循环执行次数
1for(j=1;j<=n;j++)nn
212^1for(j=1;j<=n;j++)nn
222^2for(j=1;j<=n;j++)nn
⋯\cdots⋯\cdots⋯\cdots
2t2^tfor(j=1;j<=n;j++)nn

进入外层循环的条件是 k≤nk\le n,当循环结束时,循环变量的幂次 tt 满足 2t≤n<2t+12^t\le n<2^{t+1},即 t≤log⁡2nt\le\log_2 n,所以总执行次数 T=n(t+1)=n(log⁡2n+1)T=n(t+1)=n(\log_2 n+1),时间复杂度为 O(nlog⁡2n)O(n\log_2 n)。

单项选择题 15

原书题目P8 · 解析P10 · 目视转录

【2017 统考真题】下列函数的时间复杂度是( )。

int func(int n){
    int i=0, sum=0;
    while(sum<n) sum += ++i;
    return i;
}

A. O(log⁡2n)O(\log_2 n)

B. O(n1/2)O(n^{1/2})

C. O(n)O(n)

D. O(nlog⁡2n)O(n\log_2 n)

查看答案与解析

答案:B。

基本运算为 sum+=++i,等价于“++i; sum=sum+i”,每执行一次,ii 都自增 1。当 i=1i=1 时,sum=0+1\mathrm{sum}=0+1;当 i=2i=2 时,sum=0+1+2\mathrm{sum}=0+1+2;当 i=3i=3 时,sum=0+1+2+3\mathrm{sum}=0+1+2+3。以此类推,得出 sum=0+1+2+3+⋯+i=(1+i)i/2\mathrm{sum}=0+1+2+3+\cdots+i=(1+i)i/2,可知循环次数 tt 满足 (1+t)t/2<n(1+t)t/2<n,故时间复杂度为 O(n1/2)O(n^{1/2})。

注意:统考真题中常将 log⁡2\log_2 书写为 log⁡\log,此时默认底数为 2。

单项选择题 16

原书题目P8 · 解析P10 · 目视转录

【2019 统考真题】设 nn 是描述问题规模的非负整数,下列程序段的时间复杂度是( )。

x=0;
while(n>=(x+1)*(x+1))
    x=x+1;

A. O(log⁡2n)O(\log_2 n)

B. O(n1/2)O(n^{1/2})

C. O(n)O(n)

D. O(n2)O(n^2)

查看答案与解析

答案:B。

假设第 kk 次循环终止,则第 kk 次执行时,(x+1)2>n(x+1)^2>n,xx 的初始值为 0,第 kk 次判断时,x=k−1x=k-1,即 k2>nk^2>n,k>nk>\sqrt n,因此该程序段的时间复杂度为 O(n1/2)O(n^{1/2})。

单项选择题 17

原书题目P8 · 解析P10 · 目视转录

【2022 统考真题】下列程序段的时间复杂度是( )。

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

A. O(log⁡2n)O(\log_2 n)

B. O(n)O(n)

C. O(nlog⁡2n)O(n\log_2 n)

D. O(n2)O(n^2)

查看答案与解析

答案:B。

对于单层循环如 for(j=0;j<i;j++) sum++;,可以直接数出执行次数为 ii,因此可将多层循环转换成多个并列的单层循环,且列出每个单层循环如下(假设 tt 为循环变量的幂次):

循环变量 ii单层循环语句单层循环执行次数
1for(j=0;j<1;j++)1
212^1for(j=0;j<2;j++)2
222^2for(j=0;j<4;j++)4
⋯\cdots⋯\cdots⋯\cdots
2t2^tfor(j=0;j<pow(2,t);j++)2t2^t

进入外层循环的条件是 i<ni<n,当循环结束时,循环变量的幂次 tt 满足 2t<n≤2t+12^t<n\le2^{t+1}。总执行次数 T=1+21+22+⋯+2t=2t+1−1T=1+2^1+2^2+\cdots+2^t=2^{t+1}-1,即 n−1≤T<2n−1n-1\le T<2n-1,所以时间复杂度为 O(n)O(n)。

综合应用题

综合应用题 01

原书题目P8 · 解析P11 · 目视转录

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

①

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=0;i<n;i++)
    for(j=0;j<m;j++)
        a[i][j]=0;
查看答案与解析

① 基本语句 k=k+10*i 共执行了 n−2n-2 次,所以 T(n)=O(n)T(n)=O(n)。

② 设循环体共执行 tt 次,每循环一次,循环变量 yy 加 1,最终 t=yt=y。由 t2≤nt^2\le n,得 T(n)=O(n1/2)T(n)=O(n^{1/2})。

③ 内循环执行 mm 次,外循环执行 nn 次,根据乘法原理,共执行了 m×nm\times n 次,故 T(m,n)=O(m×n)T(m,n)=O(m\times n)。