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

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

1. A2 秒
2. B8 秒
3. C1 秒
4. D4 秒

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

1. A约 n 次
2. B约 log₂ n 次
3. C约 n² 次
4. D约 n / 2 次

哪种排序算法会反复交换顺序错误的相邻元素？

1. A归并排序（Merge sort）
2. B堆排序（Heap sort）
3. C快速排序（Quicksort）
4. D冒泡排序（Bubble sort）

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

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

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

基于比较的排序在最坏情况下的下界是：

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

取一个极大匹配中每条边的两个端点，可以得到一个顶点覆盖。这个覆盖有多好？

1. A至多是最小顶点覆盖大小的两倍
2. B总是一个最小顶点覆盖
3. C与最优解相比质量未知
4. D至多是最小值的 log n 倍

Karatsuba 乘法满足 T(n) = 3T(n/2) + O(n)。它的解是什么？

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