# 1. 将 log(n!)、n log n、2^(log n)、n^(1/ε)（ε→0+）、(log n)^log n、n^(1/log n) 按渐近增长率从低到高排序，并给出关键比较步骤 A n^(1/ε)（ε→0+）实际是线性增长 B 2^(log n) 增长快于 n² C (log n)^log n ~ n log n，两者同阶 D n^(1/log n) 化简为常数 2，是其中增长最慢的 ✓ 正确答案
# 2. f(n)=o(g(n)) 与 f(n)=O(g(n)) 的本质区别是什么？举例说明存在 f,g 使得 f=O(g) 但 f≠o(g) A 若 f=O(g) 则必然 f=o(g) B O(g) 与 o(g) 完全等价，只是写法不同 C o(g) 要求 f 与 g 同阶，O(g) 要求 f 严格小于 g D O(g) 允许 f 与 g 同阶到差常数因子，o(g) 要求 f/g→0，故 f=g 时 f=O(g) 但 f≠o(g) ✓ 正确答案
# 3. 为什么算法分析中通常关注最坏情况 O 而非 Θ？什么场景下 Θ 更有信息量 A O 只关注最好情况，Θ 关注最坏情况 B Θ 比 O 更保守，应始终优先用 Θ C 算法性能随输入波动时常用 O 报最坏上界；当所有输入复杂度一致时 Θ 更有信息量 ✓ 正确答案 D 快速排序在所有输入上都是 Θ(n log n)
# 4. 渐近记号与算法工程的关系中 O(n log n) 但常数巨大的算法可能输给 O(n²) 的小常数实现，何时以实测为准？ A 渐近记号忽略常数因子，故常数巨大的 O(n log n) 算法在小规模输入上可能输给小常数的 O(n²) 算法，需要实测取舍 ✓ 正确答案 B O(n log n) 在任何输入规模上恒优于 O(n²) C 常数因子只影响 O 记号，不影响 Θ 记号 D 缓存和内存局部性对渐近复杂度无影响
# 5. 渐近记号在算法分析中的常见误用中不能对具体输入规模断言 O 界，平均情况如何定义？ A O(n) 表示 n=100 时运行时间恰为 100 个单位 B 渐近记号描述函数随 n 趋于无穷的增长率，不能对具体输入规模断言 O 界；平均情况需明确输入分布假设 ✓ 正确答案 C 平均情况与输入分布无关，总是等于最坏情况 D 渐近记号只对有限规模的 n 有效
# 6. 平均/最坏/期望复杂度的区分中以快速排序为例说明三者差异？ A 快速排序所有情况都是 Θ(n log n) B 最坏 Θ(n²)（如已排序输入且选首元素为 pivot），平均与随机化期望均为 Θ(n log n) ✓ 正确答案 C 平均情况等于最坏情况，都是 Θ(n²) D 随机化快速排序的最坏情况也降为 Θ(n log n)
# 7. 迭代函数 f(n)=f(f(n-1)) 与渐近分析的边界中为什么递归深度与调用栈大小会影响实际复杂度分析？ A 渐近分析完全忽略递归深度，不影响任何实现 B 递归深度即调用栈空间，是空间复杂度的一部分，深度 O(n) 的递归在工程中可能栈溢出，需考虑迭代或显式栈 ✓ 正确答案 C 所有递归深度都是 O(log n)，不会栈溢出 D 递归深度只影响空间，不影响算法能否运行
# 8. 2^n 与 n! 哪个增长更快？用 Stirling 公式给出严格渐近比较 A n! ~ 2^n，二者渐近相等 B 2^n 增长快于 n! C 两者同阶，都是 Θ(n^n) D n! 增长快于 2^n，由 Stirling 公式 ln(n!)≈n ln n−n 与 ln(2^n)=n ln 2 的比较可得 n!=ω(2^n) ✓ 正确答案
# 9. 常见误区中'f(n)=O(n²) 意味着 f 永远不会超过 n²'——请指出错误并给出反例 A O(n²) 要求 f(n)≤n² 对每个 n 都成立 B O(n²) 只保证存在 c>0、n₀ 使 n≥n₀ 时 f(n)≤c·n²，f 可能在部分 n 上超过 n²（如 f=2n²） ✓ 正确答案 C O(n²) 表示 f 与 n² 严格相等 D O(n²) 只适用于多项式函数
# 10. 斯特林公式证明 n! 与 (n/e)^n 的渐近关系中如何用积分近似或对数求和得到 ln(n!) ≈ n ln n - n？ A n! 与 (n/e)^n 相差一个指数因子，不可等价 B 斯特林公式给出 ln(n!)≈n²，与 (n/e)^n 无关 C 对数求和无法用积分逼近，必须用数值方法 D 用积分逼近 Σ ln k，因 ln k 单调，可得 ln(n!)≈n ln n−n，进而 n!~√(2πn)(n/e)^n ✓ 正确答案
# 11. 若 f(n)=O(g(n)) 且 g(n)=O(h(n))，证明 f(n)=O(h(n))（传递性）。类似地，Θ 是否具有对称性与自反性 A O 与 Θ 都不满足任何代数性质 B O 不满足传递性，Θ 不满足自反性 C Θ 只满足对称性，不满足自反性 D O 满足传递性（f=O(g) 且 g=O(h) 则 f=O(h)），Θ 满足自反、对称与传递 ✓ 正确答案
# 12. O/Ω/Θ/ο/ω 五类渐近记号的严格定义与区别中如何用极限比值法判定两个函数的关系？ A Θ(g) 要求 f 只满足上界，不要求下界 B o(g) 与 ω(g) 定义相同，都要求 f/g 有界 C 极限比值法在极限不存在时仍总是可用 D 若 lim f/g=0 则 f=o(g)，若 0<lim f/g<∞ 则 f=Θ(g)，若 lim f/g=∞ 则 f=ω(g) ✓ 正确答案
# 13. 常见函数增长速度排序中 log n、√n、n、n log n、n²、2ⁿ、n! 的对比与证明方法？ A √n 增长快于 n B log n < √n < n < n log n < n² < 2ⁿ < n!，可用取对数与极限比值证明 ✓ 正确答案 C n² 增长快于 2ⁿ D n! 增长慢于 2ⁿ
# 14. 复杂度比较的常用技巧中取对数比较 n^a 与 b^n、log n 与 n^ε 的大小？ A 取对数会改变函数的大小关系，不可用于比较 B 取对数后 n^a 与 b^n 大小不变，无法比较 C 多项式增长快于指数，对数增长快于多项式 D 取对数后 b^n 变为线性 n·ln b、n^a 变为 a·ln n，故 b^n≫n^a；同样 n^ε≫log n ✓ 正确答案
# 15. 用极限定义证明，若 lim_{n→∞} f(n)/g(n) = 0，则 f(n)=o(g(n))；若极限为非零常数则 f=Θ(g) A 若 lim f/g=0 则 f=o(g)；若 lim f/g=L（0<L<∞）则 f=Θ(g)，可由 ε−δ 论证推出 ✓ 正确答案 B 若 lim f/g=0 则 f=Θ(g) C 只要极限存在，f 必为 Θ(g) D 极限比值法只能证明 o，不能证明 Θ
# 16. 证明 n² + 3n + 1 = Θ(n²)，找出满足定义的常数 c1、c2 与 n0，并说明为何不能取 c1 = c2 = 1 A 下界常数必须大于上界常数 B 可取 c₁=c₂=1，因为 f(n) 恒等于 n² C 该函数不是 Θ(n²)，而是 Θ(n³) D 可取 c₁=1、c₂=5、n₀=1，但不可取 c₁=c₂=1，因为 f(n)>n² 使上界 n² 不成立 ✓ 正确答案
# 17. 请给出 O、Θ、Ω、o、ω 五种渐近记号的形式化定义（基于正常数 c 与 n0 的不等式），并各举一个满足该关系但不满足更强关系的函数对 A Θ 比 O 更弱，因为 Θ 只要求上界 B O 与 o 的定义完全相同 C O/Ω 要求存在某个 c>0，o/ω 要求对任意 c>0 成立；f(n)=g(n) 时 f=O(g) 但 f≠o(g) ✓ 正确答案 D o 与 ω 等价，都要求 f/g 有界
# 18. 如何用取对数的方式比较 n^log n 与 (log n)^n 的大小？ A n^(log n) 更大，因为 log n 的幂更高 B 取对数得 ln(n^(log n))=Θ((ln n)²)、ln((log n)^n)=n·ln(log n)，后者更大，故 (log n)^n≫n^(log n) ✓ 正确答案 C 两者同阶，都是 Θ(n log n) D 取对数后无法比较，需用数值方法
