算法与复杂度练习卷（附答案）

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A常数
2. B平方
3. C线性
4. D对数

什么是递归？

1. A永远不会结束的循环
2. B一种数据结构
3. C一种排序方法
4. D在更小的输入上调用自身的函数

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它只能运行一次
2. B它总是恰好花费一秒
3. C它的运行时间不随输入规模增长
4. D它每秒运行时间恰好处理一个元素

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

1. AO(n³)
2. BO(n log n)
3. CO(n)
4. DO(n²)

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

1. A约 20 次
2. B约 500,000 次
3. C约 100 次
4. D约 1,000 次

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

1. AO(log n)
2. BO(n²)
3. CO(2ⁿ)
4. DO(n)

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

1. A不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
2. B矛盾，但仅对长度小于 100 的数组
3. C矛盾，因此这个下界是错的
4. D不矛盾，因为插入排序不是比较排序

2²ⁿ 属于 O(2ⁿ) 吗？

1. A不属于，因为 2²ⁿ = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
2. B属于，因为两者都是指数级的
3. C不属于，因为 2²ⁿ 增长得比 2ⁿ 慢
4. D属于，因为在 Big O 中指数里的常数因子总是被忽略