算法选择题：复杂度、排序与解题方法（5 题）
001 以下代码对长度为 n 的数组执行操作，时间复杂度是多少？
难度： 基础
给定代码：
int sum = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
sum += a[j];
}
}- A. 总执行次数与 n 无关，复杂度为 O(1)
- B. 内层循环的起点随 i 后移，总执行次数为 1+2+…+n = n(n+1)/2，复杂度为 O(n²)
- C. 内层每次执行 n 次，总次数为 O(n)，因为只需统计外层循环
- D. 外层 O(n)、内层 O(n)，加起来是 O(2n) 即 O(n)
查看答案与解析
正确答案B
正确原因： 顺序代码取主导项，真正嵌套且相互独立的循环通常相乘；当循环边界相关时必须按实际执行次数求和。这里内层从 i 开始，总次数约为 n²/2，仍是 O(n²)，但推导必须基于实际次数。
错误选项辨析： A 项：两层循环都依赖输入规模，不可能与 n 无关；C 项：把内层执行次数当成常数，忽略了内层次数随 i 变化；D 项：真正嵌套的循环应相乘而不是相加，且内层次数并非固定 n 次。
002 对空 List<int> 连续执行 n 次 Add，关于总成本的说法正确的是？
难度： 进阶
- A. 容量按倍数扩容时，n 次 Add 的总成本为 O(n)，平均到每次是摊还 O(1)；某次触发扩容的 Add 单次可能达到 O(n)
- B. 扩容后旧数据会被丢弃，所以总成本与 n 无关
- C. 每次 Add 都严格 O(1)，扩容不会影响任何单次成本
- D. n 次 Add 的总成本是 O(n²)，因为每次扩容都要复制全部元素
查看答案与解析
正确答案A
正确原因： 摊还分析把一系列操作的总成本均摊到每次操作；容量翻倍策略下复制总成本为 O(n)，因此平均 O(1)，但单次扩容仍可能是 O(n)。
错误选项辨析： B 项：扩容必须把旧元素复制到新数组，复制成本正是摊还分析的对象；C 项：把摊还结论当成逐次保证，忽略了扩容时的复制成本；D 项：容量翻倍使复制总成本保持 O(n)，并非每次扩容都复制 n 个元素。
003 先按价格升序排序，再按销量降序排序，要求销量相同时仍保持价格升序，应如何理解排序稳定性？
难度： 进阶
- A. 稳定排序指无论输入如何，输出顺序都完全一样
- B. 只要最终排序结果相同，就说明算法是稳定的
- C. 应选择稳定排序，使第二次排序时相等键（销量）保持第一次排序（价格）的原始相对顺序；稳定性只在业务依赖次级顺序时才影响结果
- D. 稳定排序的时间复杂度一定高于不稳定排序
查看答案与解析
正确答案C
正确原因： 稳定排序会保持相等键元素的原始相对顺序；只有业务依赖次级顺序时稳定性才影响结果，例如销量相等时必须保持价格顺序。
错误选项辨析： A 项：把稳定性误解为输出确定性；稳定是指相等键保持输入时的相对顺序；B 项：稳定性取决于相等键元素的相对顺序是否保留，与结果集合相同无关；D 项：稳定性与复杂度相互独立，例如归并排序稳定且为 O(n log n)。
004 内存约 256MB，需要对 10 亿条 int 记录去重并统计频次，最稳妥的方案是？
难度： 进阶
- A. 先完整排序再统计，排序后的数据一定能放入内存
- B. 用 HashSet<int> 去重即可，不需要考虑内存
- C. 直接在内存中建 Dictionary<int,long>，10 亿条记录没有问题
- D. 先估算内存：10 亿规模的哈希表远超 256MB，应改用分片落盘、外部排序或近似计数等方案，并明确精度要求
查看答案与解析
正确答案D
正确原因： 输入规模与数据结构决定可接受的复杂度上限；同一问题在不同约束下可能选择不同算法。这里先估算内存是选型前提，约束不满足时要改用外部排序或分片方案。
错误选项辨析： A 项：排序仍需容纳全部数据，内存约束不会因为先排序而消失；B 项：去重后仍可能保留上亿个不同值，哈希结构的内存占用同样不可忽略；C 项：每条记录占用数十字节，10 亿条需要数十 GB，远超 256MB 约束。
005 关于递归算法的空间复杂度，哪种说法准确？
难度： 综合
- A. 递归调用栈属于额外空间并随最大递归深度增长，深度为 n 时栈空间为 O(n)；是否计入返回结果空间需要按题目口径说明
- B. 递归深度与输入无关，栈空间恒为 O(log n)
- C. 没有显式分配集合就一定是 O(1) 空间
- D. 递归返回后调用栈立即释放，因此递归空间恒为 O(1)
查看答案与解析
正确答案A
正确原因： 递归调用栈属于额外空间并随最大递归深度增长；是否计入返回结果空间需要按题目口径说明。
错误选项辨析： B 项：深度由递归结构决定，退化输入下可达 O(n)，并非恒为 O(log n)；C 项：忽略了递归调用栈本身占用的空间；D 项：空间分析看的是峰值深度，与最终是否释放无关。