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

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

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

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

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

什么是记忆化（memoisation）？

1. A在每行代码旁边写注释
2. B函数返回后释放内存
3. C存储函数调用的结果，使重复调用能直接从内存中得到答案
4. D自动把递归转换为等价的循环，从而不需要调用栈

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

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

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

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

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

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

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

为什么在有序数组中任何基于比较的查找在最坏情况下都需要 Ω(log n) 次比较？

1. A每次比较都需要对数时间
2. B有 n 种可能结果的决策树，其深度至少为 log₂ n
3. C二分查找是唯一可能的算法，它需要 log₂ n 次比较
4. D每个元素都必须至少比较一次