动态数组

形式陈述 ​

动态数组维护长度 $n$、容量 $C$ 与一块可容纳 $C$ 个元素的连续存储，始终满足 $0\le n\le C$；前 $n$ 个槽位构成逻辑序列，其余槽位是尚未使用的容量。按下标读取仍为 $O(1)$。尾部追加在 $n<C$ 时只写入一个槽位；在 $n=C$ 时分配容量 $C^{\prime }=\gamma C$ 的新区块，其中常数 $\gamma >1$，复制现有元素后再追加。单次扩容需 $\mathrm{\Theta }(n)$，但从空表连续进行 $m$ 次追加的总成本为 $O(m)$，故追加的摊还成本公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。为 $O(1)$。

以容量翻倍为例，扩容时复制的元素数至多为

$$1+2+4+\cdots +2^{\lfloor {\log }_{2}m\rfloor }<2m.$$

加上每次追加自身的一次写入，总工作量仍为线性。若支持自动收缩，收缩阈值必须低于扩张阈值，例如装载率降到 $1/4$ 时把容量减半；这样收缩后装载率回到 $1/2$，为下一次扩容留出足够间隔。

直觉 ​

动态数组用空余空间购买增长余地。大多数追加只占用已经预留的下一个槽位，偶尔才整体搬家；昂贵搬迁不是消失了，而是由此前一长串便宜操作共同分摊。容量按常数因子增长的关键在于：每次搬迁后，新空位与已有元素同量级，所以在再次搬迁前必然发生足够多的新追加。

连续布局保留了普通数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。的地址计算与缓存局部性，却也继承了它的限制。中间插入或删除会改变后缀元素的位置，通常仍需 $\mathrm{\Theta }(n)$ 次搬移；“可变长”只解决容量管理，不会让所有位置的修改都变成常数时间。

例子与边界 ​

从容量 $1$ 开始依次追加元素，容量沿 $1,2,4,8,\dots$ 增长。追加第五个元素时，容量从 $4$ 扩为 $8$，这次操作复制四个旧元素后再写入新元素，明显不是最坏 $O(1)$；但前四次追加已经跨过了足够多的便宜步骤，整段序列的总复制量受几何级数控制。对需要稳定低延迟的程序，这种摊还保证仍可能不够，因为某一次暂停会随数组大小增长。

若每次满时只把容量增加一格，第 $k$ 次扩容要复制 $k$ 个元素，前 $m$ 次追加的复制总量为 $1+2+\cdots +(m-1)=\mathrm{\Theta }(m^2)$，摊还常数界随即消失。收缩也会造成类似问题：若在装载率恰降到 $1/2$ 时立刻缩半，那么一次删除触发收缩后，紧接着一次追加便可能再次扩张，交替操作会令结构在两个容量间反复整体复制。扩张与收缩阈值之间的滞回区正是为阻止这种抖动。

扩容还会使指向旧存储区的地址、迭代器或引用失效；哪些引用保持有效取决于语言和容器契约。容量是实现状态，不等于可观察的逻辑长度，也不能把尚未初始化的槽位当成序列成员。

推论与应用 ​

动态数组是向量、可变列表、字节缓冲区与许多哈希表桶数组的常见底层表示。它把 $O(1)$ 随机访问、良好局部性和摊还 $O(1)$ 尾部追加组合在一起；若主要操作落在两个端点，循环数组实现的双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。可避免首部操作搬移，若频繁修改中间位置则需链表或分块结构。

势能法公理库势能法Potential method用数据结构状态势能的变化修正实际成本以界定均摊成本。可把空余容量或装载率偏离目标的程度编码成势，统一证明扩张与收缩的摊还界。工程实现还需考虑增长因子对空间与复制次数的取舍：因子较大减少搬迁，代价是更多闲置空间；因子接近 $1$ 节省空位，却提高总复制量。渐近结论要求增长因子与 $1$ 保持固定距离。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§16.4, dynamic tables。
• Erik D. Demaine, MIT 6.046J, Amortization: Amortized Analysis, lecture notes，dynamic-table expansion and contraction。