下面是一段用切片实现的归并排序： ```python def msort(a): if len(a) <= 1: return a mid = len(a) // 2 left = msort(a[:mid]) right = msort(a[mid:]) return merge(left, right) ``` (1) 写出它的递归式并求时间复杂度。 (2) 这段代码的空间复杂度是多少？注意 `a[:mid]` 在 Python 中是复制而不是视图，请把每一项的来源说清楚。 (3) 如果改成传下标区间、不产生新列表的写法，时间和空间会发生什么变化？
面试官在考什么
判断候选人能否把「递归深度 × 每层空间」这种想当然的乘法拆开，正确判断切片在任意时刻的存活量，并能否用主定理而不是靠记忆回答递归式。
回答框架 · 前两步
- 递归式 T(n) = 2T(n/2) + Θ(n)：划分与合并各是线性。主定理中 log_b a = 1 与 f(n)=Θ(n) 同阶，属 case 2，得 Θ(n log n)。
- 递归调用栈深度 O(log n)，栈本身占 O(log n) 空间。
还有 3 条答案要点、 3 层追问、 5 个常见坑， 以及针对你简历的追问路径，在定制报告里。
延伸阅读
想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页
同一能力域的其他题
- 下面这段代码用于统计数组中和为某值的下标对： ```python def pairs(nums): s = set(nums) res = [] for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] in s: res.append((i, j)) return res ``` (1) 它的时间复杂度和空间复杂度分别是多少？请说明每一项是怎么算出来的。 (2) 如果线上 nums 的长度 n = 10^6，这个函数能不能直接上线？为什么？ (3) 如果 nums 中存在大量重复元素，复杂度会变吗？
- 有一个去重任务：内存中一次性有 1 亿条 URL，平均长度 80 个 ASCII 字符，要在一台 JVM 堆上限 4GB 的机器上做「精确去重」（不允许有误判，不允许落盘到外部存储作为主方案）。有人提议直接用 HashSet<String> 装全部 URL。请回答：(1) 估算这个 HashSet 的内存占用，判断是否可行，要求给出量级估算的过程而不只是结论；(2) 如果不可行，写出你实际会采用的方案，并说明它把成本转移到了哪里。
- 你负责一个日处理 50 亿条日志的离线去重系统。输入是 50 亿个 128-bit 的 ID，要求输出去重后的 ID 集合。团队提出两个方案：方案 A 用哈希表，期望 O(n) 时间和 O(n) 额外空间，单机 256 GB 内存可能放不下；方案 B 先外部排序再扫描去重，O(n log n) 时间和 O(1) 额外空间（磁盘），但需要多轮磁盘 I/O。作为技术负责人，你怎么做复杂度分析和工程选型？请给出量化估算和最终决策，并说明你会怎么向团队解释 Big-O 与实际吞吐之间的关系。
- 阅读下面的 Python 函数，n 是正整数。请分析它的时间复杂度（以 total += 1 的执行次数为准）和额外空间复杂度，并说出推导过程。 ```python def h(n): total = 0 i = 1 while i <= n: for j in range(i): total += 1 i *= 2 return total ```
- Python 的 `list.append` / C++ 的 `vector::push_back` 在容量不足时会申请更大的内存并搬移已有元素。以「容量满时容量翻倍」的策略为例： (1) 单次 append 的最坏时间复杂度是多少？ (2) 为什么文档和面试里普遍说 append 是 O(1)？请把 n 次连续 append 的总代价推出来。 (3) 如果把策略换成「每次容量不足时只加 1 个位置」，结论怎么变？ (4) 为什么工程实现里常见 ×2 或 ×1.5，而不是 ×1.1 或固定增量？
- 一个动态数组从容量 1 开始，每次写满就扩容为原来的 2 倍，并把旧元素全部拷贝到新数组。现在连续 append 100 万次（元素总数为 100 万）。请回答：(1) 整个过程总的元素拷贝次数是多少？(2) 单次 append 的最坏代价和均摊代价分别是多少？(3) 如果产品要求「任意单次操作的 P99 延迟抖动不能超过某个阈值」，这个 2 倍扩容策略有什么问题，你会怎么改？