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

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

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

f(n) = Θ(g(n)) 是什么意思？

1. Af 的增长严格快于 g
2. Bf 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
3. Cf 的增长严格慢于 g
4. D对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界

算法的最坏情况运行时间描述的是什么？

1. A在最小输入上所需的时间
2. B在所有规模为 n 的输入上所需的最长时间
3. C在规模为 n 的随机输入上所需的期望时间
4. D在慢速计算机上所需的时间

递推式 T(n) = 2T(n − 1) + O(1) 的解是什么？

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

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

递推式 T(n) = T(n − 1) + O(n) 的解是什么？

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

Strassen 算法在矩阵乘法中对半尺寸的分块只做 7 次而不是 8 次递归乘法。它的运行时间是多少？

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n^{log₂ 7})，约为 n^2.81
4. DΘ(n² log n)

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

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