有一段递归函数 f(arr, l, r)：若 r - l <= 1 直接返回；否则先用一个 O(n log n) 的排序把 arr[l..r] 这一段排好（n = r - l），然后令 m = (l+r)/2，递归调用 f(arr, l, m) 和 f(arr, m, r)。请回答：(1) 写出它的递归式，并求出 n = 2^k 时的时间复杂度；(2) 如果每次递归调用都新建一个长度为 n 的数组、把子区间拷进去并在新数组上排序，空间复杂度是多少？

面试官在考什么

能否正确使用主定理处理 f(n) 中带 log 因子的情况，以及能否区分「总分配量」和「同时存活峰值」两种空间口径。

递归复杂度

回答框架 · 前两步

1. 递归式为 T(n) = 2T(n/2) + Θ(n log n)，a = 2、b = 2，基准是 n^(log_2 2) = n，而 f(n) = n log n = Θ(n^1 · log^1 n)，属于主定理扩展第二类 k = 1 的情形，所以 T(n) = Θ(n log² n)。
2. 不能直接套归并排序的结论答成 O(n log n)：多出来的那层 log 来自「每层自身的代价里本来就带一个 log」。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、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 倍扩容策略有什么问题，你会怎么改？