题目重点：用几何扩容模型解释没有预分配的append为何仍能实现总线性时间。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 教学实现使用容量不足时翻倍的动态数组，按槽位复制计成本；不声称某语言运行时严格翻倍。存储的是对象引用，复制引用不等于深复制对象。
- 只分析append构造N个元素，不把任意位置插入、昂贵对象创建或内存分配失败也算作常数。
解题路线
- 未触发扩容时写一个槽位O(1)；容量满时分配新数组并复制当前所有引用，本次最坏O(N)。单次最坏与连续操作的平均成本是两个不同问题。
- 容量1、2、4、8依次增长时，总复制量为1+2+4+…+最后旧容量。几何级数小于2N，加上N次新元素写入，总槽位工作O(N)，故每次append摊还O(1)。
- 分配空槽位也需要计成本，几何增长使历次新容量之和仍O(N)。本例copied只计旧元素复制，并不测墙钟速度；验证指标不能偷换为完整运行时间。
- 若每次只增加固定常数容量，则复制量为线性增长数列，总成本Θ(N²)。关键是几何增长策略，不能凭“动态数组”名称就断言摊还常数。
- 预分配能减少重分配和峰值延迟，但需知道或估计N，可能浪费内存。在线输入长度未知可采用动态增长；对严格延迟要求要考虑分块结构或提前reserve的接口。
手动走一遍
追加9个元素时容量经历1/2/4/8/16，旧元素复制0+1+2+4+8=15，小于2×9。第9次本身复制8个元素，不是最坏O(1)，但9次总体仍线性。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class DoublingArray:
"""Teaching model, not a claim about a language runtime's growth factor."""
def __init__(self):
self.storage=[];self.size=0;self.copied=0
def append(self,value):
if self.size==len(self.storage):
capacity=max(1,2*len(self.storage))
grown=[None]*capacity
for i in range(self.size):grown[i]=self.storage[i]
self.copied+=self.size;self.storage=grown
self.storage[self.size]=value;self.size+=1
def values(self):
return self.storage[:self.size]
复杂度
N次append总时间O(N)，单次最坏O(N)、摊还O(1)。稳定存储O(N)，扩容期间旧数组和新数组同时存在，峰值仍O(N)但常数增加。values复制当前元素需O(N)时间与空间。
易错点与追问
容易失分的边界
- 把摊还O(1)说成每次最坏O(1)。
- 忽略容量策略，或把引用复制当任意大小对象深复制。
- 用copied计数声称实际分配器延迟已被测量。
继续深挖
- 如果增长因子是1+ε，复制次数与空闲容量之间如何权衡？
- 严格实时场景如何限制每次迁移量，并保证迭代器与引用稳定性？
