首页 › 题库 › 信息学奥赛 › 8.1 复杂度分析

信息学奥赛-提高级 题库

共 68 道题 ,第 1 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 8.1 复杂度分析 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

递归关系式T(n)=2T(n/2)+O(n²)描述了某个分治算法的时间复杂度,该算法的时间复杂度是多少?

A
O(n)
B
O(nlogn)
C
O(n2)
D
O(n2logn)
答案与解析
正确答案:C

用主定理或递归树法。递归树中:  

第1层总时间复杂度n2;  

第2层2*(n/2)2=n2/2;  

第3层4*(n/4)2=n2/4;  

……总和为n2*(1+1/2+1/4+…)≤2n2,时间复杂度为O(n2)。 

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

斐波那契数列定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2),使用朴素递归方法计算F(n)的时间复杂度是指数级的,而使用动态规划(或迭代)方法的时间复杂度是线性的,造成这种差异的根本原因是?

A
递归函数调用栈开销过大
B
操作系统对递归深度有限制
C
朴素递归中存在大量的重叠子问题未被重复利用
D
动态规划使用了更少的数据存储空间
答案与解析
正确答案:C

朴素递归会重复计算大量重叠子问题(如计算F(5)需算F(4)和F(3),算F(4)又需算F(3)和F(2)),动态规划通过存储子问题结果避免重复计算。

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

记程序结束前p数组元素的最大值为P,则该代码的时间复杂度是?

A
O(n)
B
O(mnlogmn)
C
O(mn/2logmn/2)
D
O(m3/2(log mn/2+log P))
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设一个长度为n的整数数组中每个元素互不相同,且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少?( )

A
O(n)
B
O(log n)
C
O(n log n)
D
O(1)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

在设计一个哈希表时,为了减少冲突,需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有n个键值对,表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中,最坏情况下查找一个元素的时间复杂度为( )?

A
O(1)
B
O(log n)
C
O(1/(1-α))
D
O(n)
答案与解析
正确答案:D

开放地址法当计算出来的地址被占用时,用再寻址的方法寻找下一个地址,如果还是占用就接着寻找,直到找到一个空的地址,在最坏情况下可能会遍历所有已经占用的地址

题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设n是图的顶点的个数,m是图的边的个数,为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言,下面的四个选项,哪一项的渐近时间复杂度最小

A
O(m√logn·loglogn)
B
O(n2+m)
C
O(n2/logm+mlogn)
D
O(m+nlogn)
答案与解析
正确答案:A

由于图片,m和n的增长速度完全相同,可以认为图片,C为常数。把所有m替换成n后很容易排除B、C选项。考虑另外两个选项,当x比较大时,一定有图片,同理图片,两边同乘图片得到图片,而常数不影响渐进时间复杂度,说明A比D小。

题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

现在用如下代码来计算下xn,其时间复杂度为()

double quick_power(double x, unsigned n){

        If(n  == 0) return 1;

        If(n  == 1) return x;

        return  quick_power(x, n/2)

* quick_power(x, n/2)

* ((n & 1) ? x : 1);

}
A
0(n)
B
0(1)
C
0(logn)
D
0(nlogn)
答案与解析
正确答案:A

虽然看上去使用了快速幂,但是每次分治后程序把quick_power运行了两次,没能真正实现分治法,复杂度仍然是O(n)。

题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

.solve1(n)的时间复杂度为()。

A
0(n log2 n)
B
0(n)
C
0(n logn)
D
0(nloglogn)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
9 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

solve2(n)的时间复杂度为()。

A
0(n2)
B
0(n)
C
0(n logn)
D
0(n√n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
10 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

设a数组中最大值减最小值加1为A,则f函数的时间复杂度为()。

A
0(n logA)
B
0(n2logA)
C
0(n log(nA))
D
0(nlogn)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
11 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

考虑对 n 个数进行排序,以下最坏时间复杂度低于 O(n^2)的排序方法是( )。

A
插入排序
B
冒泡排序
C
归并排序
D
快速排序
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
12 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

对于给定的 n,分析以下代码段对应的时间复杂度,其中最为准确的时间复杂度为( )。

int i, j, k = 0; 

for (i = 0; i < n; i++) { 

for (j = 0; j < n; j*=2) { 

k = k + n / 2; 

} 

}

A
O(n)
B
O(n log n)
C
O(n√n)
D
O(n2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
13 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法最坏情况下的时间复杂度为( )。

A
O(n + m)
B
O(n log m)
C
O(m log n)
D
O(nm)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
14 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

斐波那契数列的定义为:F1=1,F2=1,Fn=Fn-1+Fn-2 (n>=3)。现在用如下程序来计算斐波那契数列的第 n 项,其时间复杂度为( )。

F(n):

if n<=2 return 1

else return F(n-1) + F(n-2)

A
O(n)
B

O(n2)

C

 O(2n)

D
O(n log n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
15 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

solve1(1, n) 的时间复杂度为( )。

A
Θ(log n)
B

Θ(n)

C

Θ(n log n)

D
Θ(n^2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
16 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

solve2(1, n) 的时间复杂度为( )。

A
Θ(log n)
B
Θ(n)
C
Θ(n log n)
D
Θ(n^2)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
17 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

设输入字符串长度为 n,encode 函数的时间复杂度为( )。

A
Θ,√n
B
Θ(n)
C
Θ(n log n)
D
Θ(n^2 )
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
18 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

具有n个顶点,e条边的图釆用邻接表存储结构,进行深度优先遍历运算的 时间复杂度为()

A
0(n+e)
B
0(n^2)
C
0(e^2)
D
0(n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
19 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时,如果不使用堆或其它优先队列进行优化,则其时间复杂度为()。

A
0((m + n^2) log n)
B
0(mn + n^3)
C
0((m + n) log n)
D
0(n^2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
20 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()

A
0(n), 0(n^2)
B
0(n), 0(n log n)
C
0(n log n), 0(n^2)
D
0(n log n), 0(n log n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情