编程面试：如何实现动态数组并证明 append 的摊销 O(1)？

题干与适用场景

请使用固定数组实现一个支持 get(index)、set(index, value) 和 append(value) 的动态数组。数组满时扩容，要求说明增长策略、边界行为、append 的最坏时间与摊销时间，并比较线性扩容和几何扩容。

题目假设元素是引用或固定大小值，索引从 0 开始；越界访问抛出异常，空数组允许 append。公开面试题库把动态数组/Vector 与 Microsoft、内存管理和摊销分析联系起来；MIT 6.006 讲义则将动态数组的末尾插入列为摊销 Θ(1)。

面试官考察点

• 是否区分 size 与 capacity，并维护“有效元素都在前 size 个槽位”的不变量。
• 是否选择几何增长，而不是每次只增加一个槽位。
• 是否能用总复制量、会计法或势能法证明摊销界，而不是只背 O(1)。
• 是否说明空容量、整数溢出、内存失败、缩容和中间插入的边界。

回答前需要澄清的问题

• 只要求尾部 append，还是还要支持中间 insert、delete 和 pop？后者会改变复杂度。
• 元素是否固定大小？是否需要保留引用语义、迭代器失效规则或线程安全？
• 扩容目标是降低复制次数、节省空间，还是满足实时延迟上限？
• 是否要求 shrink？如果要求，触发阈值是否与扩容阈值分离以避免抖动？

30 秒回答框架

我会保存底层数组、size 和 capacity。append 在有空槽时直接写入；满时分配更大的数组，复制前 size 个元素，再写入新值。增长应使用固定倍数，例如翻倍：第 n 次扩容复制的总元素数是一个几何级数，小于 2n，因此 n 次 append 的总成本是 O(n)，单次摊销 O(1)。单次扩容仍然是 O(n)，这不能表述成每次最坏 O(1)。

分步骤深入解答

状态与不变量

维护三个字段：底层数组 data、有效元素数量 size、分配槽位数量 capacity。始终满足 size 不小于 0 且不大于 capacity，有效元素位于索引区间 [0, size)；append 只写入 data[size] 并把 size 加一。get 和 set 只允许访问 [0, size)，不能把尚未初始化的容量当作元素。

几何扩容策略

当 size == capacity 时，分配至少 max(1, capacity * 2) 的新数组，复制旧元素并替换引用。初始 capacity 为 0 时要特殊处理，否则乘二仍是 0。翻倍让两次扩容之间至少有与当前规模同数量级的廉价 append；增长因子越大，复制频率越低但闲置空间越多。

~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;

public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }

public int size() { return size; }

public Object get(int index) { check(index); return data[index]; }

public void set(int index, Object value) { check(index); data[index] = value; }

private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~

这里的 Object[] 只为展示泛型擦除下的常见实现；生产代码还要决定 null、内存分配失败和并发访问语义。核心不变量与复杂度不依赖 Java。

摊销证明

假设 capacity 从 1 开始翻倍，连续 append n 个元素。普通写入贡献 n 次常数成本；扩容复制发生在容量 1、2、4、8……时，总复制量低于 2n。所以总成本小于 3n 加初始化常数，n 次操作的平均成本为 O(1)。

这是对一段最坏操作序列的保证，不是输入随机时的平均值。某一次恰好触发扩容时仍然需要复制 Θ(n) 个元素，因此单次最坏时间是 O(n)，get/set 的最坏时间是 O(1)，空间是 O(n)。

线性增长与缩容

如果每次只增加 c 个槽位，插入 n 个元素会复制约 c + 2c + ... 的线性级数，总成本为 Θ(n²)，append 的摊销时间退化为 Θ(n)。几何增长通常更合适，但增长因子越大，峰值空闲空间越高。

若支持 pop，可以在 size/capacity 低于阈值时缩容；扩容阈值和缩容阈值必须分开，例如满时翻倍、低于四分之一时减半，避免“加一个、删一个”在边界反复搬迁。缩容不会改变尾部操作的摊销 O(1)，但会增加释放与复制的暂停成本。

可验证的边界

测试空数组第一次 append、容量恰好满时的 append、连续扩容、重复引用、负索引、index 等于 size、超大容量溢出和分配失败。用受控的复制计数器验证 n 次 append 的总复制量与 n 成正比；不要只测试最后的数组内容，因为线性扩容也能产生正确结果。

高质量示范回答

我会把底层数组、size 和 capacity 分开维护，并保证有效元素始终位于前 size 个位置。append 有空槽时直接写入；满时分配两倍容量、复制旧元素并继续写入。初始容量为零时至少分配一个槽位。

翻倍的关键是摊销证明：连续 n 次 append 的扩容复制量低于 2n，再加上 n 次常数写入，总成本 O(n)，所以 append 摊销 O(1)。但触发扩容的那一次最坏仍是 O(n)，不能把摊销界说成每次调用的硬延迟上限。线性增长会导致总复制 Θ(n²)；若支持缩容，我会用滞后阈值避免扩缩容抖动，并测试空输入、越界、溢出和分配失败。

常见错误

• 每次满了只加一个槽位 → 复制次数形成平方级总成本 → 使用几何增长并给出级数证明。
• 把 append 说成最坏 O(1) → 忽略扩容时的复制 → 明确区分单次最坏 O(n) 与序列摊销 O(1)。
• 用 capacity 判断 get 是否有效 → 读到未初始化槽位 → 用 index 不小于 0 且小于 size 校验。
• 初始容量为零时直接乘二 → 数组永远无法增长 → 用至少一个槽位的特殊分支。
• 低水位立即缩容 → 交替 append/pop 造成反复搬迁 → 分离扩容与缩容阈值。

追问及应对

如果要求每次 append 都有 O(1) 最坏时间怎么办？

普通连续数组扩容会产生 O(n) 搬迁，不能承诺每次硬上限。可以分段数组、增量搬迁或预先分配上界，但会牺牲连续内存、索引常数或空间；先确认延迟目标是否真的要求 worst-case。

增长因子从 2 改成 1.25 有什么变化？

只要增长因子严格大于 1，尾部 append 仍可摊销 O(1)，但复制更频繁、额外空间更少。增长因子接近 1 时常数项变大；选择应结合内存预算、分配器行为和延迟目标，而不是只比较 Big-O。

如何证明线性增长是 O(n²)？

每次扩容只增加 c 个位置时，第 j 次扩容大约复制 jc 个元素；前 n 个元素需要约 n/c 次扩容，复制总和是 c + 2c + ... + (n/c)c = Θ(n²)。因此每次 append 的摊销成本是 Θ(n)。

支持中间 insert 后复杂度如何变化？

即使容量充足，中间插入也要把后缀元素右移，最坏 O(n)。扩容复制只是额外成本；动态数组的优势仍是随机访问和尾部操作，不应把所有 insert 都归为 O(1)。

多线程同时 append 如何处理？

需要锁、单线程 owner 或原子索引加安全扩容协议。仅把 size 声明为原子并不能保护“检查容量、分配、复制、替换”这一整段；如果题目没有并发要求，应先明确单线程边界。