实现一个动态数组：初始容量为 1，当已存元素个数超过当前容量时，申请一个容量翻倍的新数组，把旧元素逐个拷贝过去，然后放入新元素。现在连续执行 n 次 push_back（n 是 2 的幂）。请回答：(1) 这 n 次操作一共发生多少次元素拷贝？(2) 单次 push_back 的最坏代价是多少？(3) 均摊到每次操作的代价是多少，为什么？

面试官在考什么

是否理解均摊分析是对一个操作序列求和再除以次数，而不是概率意义下的平均；以及能否区分“单次最坏 O(n)”和“均摊 O(1)”。

均摊分析

回答框架 · 前两步

1. 扩容发生在容量 1→2→4→…→n 时，总拷贝次数是 1+2+4+…+n/2 = n−1，小于 n，而不是每次扩容都拷贝 n 个。
2. 单次 push_back 的最坏代价是触发扩容的那一次，O(n)。

延伸阅读

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