帆软 10.15 笔试附加题：两道场景题的复杂度分析

《面试题目》

1. 附加题时长 60 分钟，共 2 道简答题；题目都是给出一个具体场景，要求分析时间复杂度和空间复杂度。

《参考解析》

复杂度类简答题按「结论先行 + 推导 + 边界」三段写。 先一句给出结论（如「时间复杂度 O(n log n)，空间复杂度 O(n)，来自排序与结果数组」），再写推导过程，别让阅卷人从你的算式里猜答案。推导时把变量定义清楚：n 是什么、m 是什么，分清是数据规模还是值域；循环嵌套逐层相乘，但要注意内层循环的次数是否依赖外层（比如 for i in 0..n: for j in 0..i 是 O(n²)，而滑动窗口的内层指针总量是 O(n)，看上去两层其实是 O(n)）——这类「看似双循环实为线性」是场景题最爱考的陷阱。

把最好、最坏、平均三种情况分开说，并说明依赖哪个输入特征。 比如快排平均 O(n log n)、最坏 O(n²)（已排序且取首元素为枢轴），哈希表平均 O(1)、最坏 O(n)（全部冲突）。摊还分析也要点一句：动态数组扩容单次是 O(n)，但连续 n 次插入摊还下来仍是 O(1)；并查集加了按秩合并和路径压缩后接近 O(1)。空间复杂度别只算辅助数组，递归调用栈、字符串拼接产生的临时对象、以及是否允许修改输入都要写清楚——常见追问就是「能不能做到 O(1) 额外空间」（原地交换或双指针）和「如果输入不能改怎么办」。