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

当 n 变大时，下列哪一项增长最慢？

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

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

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

在已经有序的数组上，插入排序的最好情况时间复杂度是多少？

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

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

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

1. A常数
2. B指数级
3. C线性
4. D对数级

当问题具有以下特征时，动态规划（dynamic programming）很有用：

1. A完全没有子问题，因此一步就能解决
2. B重叠子问题和最优子结构
3. C只有随机输入
4. D只有一个循环

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

1. A0/1 背包问题，物品必须整个拿取
2. B两种变体都不可以
3. C两种变体都可以
4. D分数背包问题，物品可以分割

Cook–Levin 定理确立了什么？

1. A布尔可满足性问题（SAT）是 NP 完全的
2. B每个 NP 问题都能在指数时间内求解
3. C停机问题是不可判定的
4. DP 不等于 NP