归并排序的递归式为：T(1) = 1；当 n > 1 时 T(n) = 2T(n/2) + n（最后的 n 是合并两个有序子数组的代价）。请回答：(1) 画出递归树，每一层所有子问题上的代价加起来是多少，树有多少层？(2) 时间复杂度是多少？(3) 这个递归排序过程的额外空间复杂度是多少，由哪几部分组成？

面试官在考什么

能否用递归树把“每层代价 × 层数”算清楚，而不是凭印象报一个 O(n log n)；以及能否把递归栈深度也算进空间复杂度。

递归复杂度

回答框架 · 前两步

1. 第 k 层有 2^k 个子问题，每个规模 n/2^k，各层合并代价之和恒为 n：因为每一层只是把 n 个元素分到不同子问题里，合并时每个元素被扫描一次。
2. 当 n/2^k = 1 时 k = log2 n，所以树有 log2 n + 1 层。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 下面这段代码用于统计数组中和为某值的下标对： ```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 倍扩容策略有什么问题，你会怎么改？