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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

1. A9 秒
2. B12 秒
3. C6 秒
4. D3 秒

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

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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

1. A8 秒
2. B2 秒
3. C4 秒
4. D1 秒

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

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

为什么动态规划不能真正加速归并排序？

1. A归并排序已经是 O(n)
2. B归并排序没有递归结构
3. C动态规划只适用于图问题，不适用于数组
4. D它的子问题不重叠，因此没有可以复用的结果

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

1. A选择总是需要 Ω(n log n)，因为必须先排序
2. B选择只能在 O(n²) 内完成
3. C快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)
4. D快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

1. A因为它只适用于 W = 0
2. BW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
3. C因为该算法是随机化的，其运行时间随每个输入而变化
4. D因为 n 总是很小