首页 › 题库 › 信息学奥赛 › 8 算法复杂度与优化

信息学奥赛-提高级 题库

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

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

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

(3分)若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是( )。

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

最坏情况下,此程序的时间复杂度是( )。

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

此程序的时间复杂度是( )

A
O(n)
B
O(log n)
C
O(n^2)
D
O(n log n)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
45 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 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
这道题暂未补解析。
题目详情
46 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

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

A
Θ(log n)
B

Θ(n)

C

Θ(n log n)

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

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

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

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

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

设某算法的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n(n 为正整数)及 T(0) = 1,则该算法的时间复杂度为( )。

A
O(log n)
B
O(n log n)
C
O(n)
D
O(n^2)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
50 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设数组c长度无限制,该程序所实现的算法的时间复杂度是O(b)的( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
51 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设输入的s是包含n个字符的01串,函数solve()所实现的算法时间复杂度是O(n*2m)()

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
52 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

假设程序运行前能自动将maxn改为n+1,所实现的算法的时间复杂度是O(nlogn)()

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
53 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的空间复杂度仅与 n 有关。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
54 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的时间复杂度为 O(m(n + k))。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
55 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的时间复杂度为 O(logk n)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
56 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

若两个字符串的长度均为n,则最坏情况下,此程序的时间复杂度为 0(n!)。 ()

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
57 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

若两个字符串的长度均为n,则最坏情况下,此程序的时间复杂度为 0(n!)。 ()

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
58 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的空间复杂度仅与 n 有关。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
59 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的时间复杂度为 O(m(n + k))。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
60 判断题 偏易 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

该算法的时间复杂度为 O(logk n)。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情