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

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

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

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

哪种记号表示增长的下界？

1. AΩ（Big Omega）
2. Bo（little o）
3. CO（Big O）
4. DΘ（Big Theta）

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

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

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

1. A编译器总会把它变成能安全结束的循环
2. B它会不断调用自身，直到调用栈溢出
3. C它会自动返回 0
4. D它的运行时间为 O(1)

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

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

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

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

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

1. AO(n!)
2. BO(n² 2ⁿ)
3. CO(n³)
4. DO(2^n²)