一个容量已满的数组追加元素时，可能需要复制全部旧元素。这次操作的线性成本，与一长段追加操作具有线性总成本可以同时成立。摊还分析说明每段合法序列的总账，不要求用户随机操作，也不把昂贵调用的延迟抹掉。

第 02 篇通过求和分析递归，本篇把相同方法用于数据结构的时间序列。讨论对象是抽象动态数组：当前元素数 n、容量 C、操作序列长度 q，C 初始为 1，始终为 2 的幂。只支持末尾追加与删除；中间插删需要移动元素，不属于本篇常数摊还结论。

满时加倍的总复制成本

追加前若 n=C，就分配容量 2C 的存储，复制 n 个已有元素，然后写入新元素。一次普通追加计 1 次写入，一次扩容追加计 n+1 次。这里按存活元素复制收费，未计清零新容量的工作；若分配还需 $\Theta(C)$ 初始化，常数会变化，总阶的论证仍需把它纳入。

从空数组开始连续追加 q 次，复制发生在容量 1、2、4、8 等时刻。设最后一次复制的旧容量为 $2^t<q$ ，总复制数为：

1+2+\cdots+2^t=2^{t+1}-1<2q.

加上 q 次新元素写入，总成本小于 3q。因此 q 次追加的总成本 O(q)，摊还每次 O(1)。q=0 和 q=1 单独看显然满足常数边界；不应为了写对数而给它们套一个未定义式。

单次最坏仍然是 Θ(n)。如果服务请求必须在固定上限内返回，摊还保证本身不能替代延迟上界。可以另研究分批迁移，但那会引入新旧两份数组的访问规则，不在当前教学实现范围内。

记账怎样覆盖复制

每次追加收取 3 个单位，其中 1 个支付本次写入，剩下的积累为信用。扩容后，到下一次填满为止会增加约 C 个元素，而下一次扩容要复制约 2C 个元素。每个普通追加留下 2 个信用，能够支付那次复制。最初容量 1 的边界可直接核对。

记账法要证明信用从不透支。不能仅说“平时存钱，贵时花钱”，却不写两次昂贵操作之间至少有多少次便宜操作。扩容倍率大于 1 且固定，正是这里能够积累线性数量信用的原因。若每次只增加一个容量，总复制会变成 $1+2+\cdots+(q-1)=\Theta(q^2)$ 。

这种归因适合解释成本来自何处；势能法把信用直接写成状态函数，便于处理既增加又减少的序列。

势能是状态里的未结算成本

设第 i 次操作实际成本为 $c_i$ ，前后状态势能为 $\Phi_{i-1},\Phi_i$ ，定义摊还成本 $\hat c_i=c_i+\Phi_i-\Phi_{i-1}$ 。求和后中间势能抵消：

\sum_{i=1}^{q}c_i=\sum_{i=1}^{q}\hat c_i+\Phi_0-\Phi_q.

若势能非负且初始势能是常数，摊还成本的总和就给出实际成本总和的上界，加一个初始常数。若从一个已经装满的大数组开始，必须保留 $\Phi_0$ ；省掉它会把建立初始状态的工作凭空消除。

只追加时，扩容后数组至少约半满，势能可以采用 2n-C 并单独处理初始空状态。为统一讨论删除，直接采用非负的分段势能：

\Phi(n,C)= \begin{cases} 2n-C,&n\ge C/2,\\ C/2-n,&n<C/2. \end{cases}

两段在半满处都为零。数组越接近满，势能越大，预付扩容成本；数组越稀疏，另一段开始积累收缩成本。初态 (0,1) 的势能为 1/2，是一个常数。

为什么在四分之一处缩容

删除末尾元素先令 n 减 1；若 C>1 且新 n≤C/4，就把容量减半，复制余下 n 个元素。合法操作从空表开始，空表删除抛 IndexError。扩容后的装载率约为 1/2，收缩后的装载率也约为 1/2，因而距离下一次反向调整有余量。MIT 的动态数组讲义把收缩阈值低于重分配后的填充率作为关键条件。MIT 6.006 Lecture 2

对 C≥4 的收缩操作，删除前 n=C/4+1，删除后 n’=C/4，容量变为 C’=C/2。操作前势能为 C/4-1，操作后为 0；实际成本为 1+C/4，所以摊还成本为 2。

对扩容操作，操作前 n=C，势能为 C；操作后 n’=C+1、C’=2C，势能为 2。实际成本 C+1，摊还成本为 3。不发生调整的追加，势能增长至多 2；不发生调整的删除，势能增长至多 1。容量 1、2 的少数跨段情形逐个代入仍为常数。

因此任意合法末尾增删序列的每次摊还成本都被同一个常数控制，总成本 O(q)，而不是仅对“先全部追加，再全部删除”的顺序成立。容量始终在元素数的常数倍附近，存储为 O(n+1)；按本模型，单次调整仍可能需要 Θ(n) 工作。

半满即缩容的反例

将规则改为“删除后 n≤C/2 就容量减半”。从 n=C=m 的满数组开始，追加一项会扩容到 2m，复制 m 个元素；随后删除刚追加的项，n 回到 m，半满规则立即缩回 m，再复制 m 个元素。

重复 append、pop，每两次操作都复制 2m 个元素。在初始 m 次建表之后进行 r 对操作，总成本包含 Θ(rm)，不能由总操作数 m+2r 的常数倍统一约束。选 r=m 就得到二次复制量。这给出了任意规模的反例族；某个固定 m 的运行只是其中一例。

用四分之一规则执行相同序列，第一次扩到 2m 后，n 在 m 与 m+1 之间变化，不再收缩。两条规则都能保存正确内容，但成本保证不同，所以仅检查最终元素相等无法发现这个性能缺陷。

操作模拟能观察到什么

1	`python3 examples/advanced-algorithms/check_foundations.py`

dynamic_array.py 只维护逻辑元素数、容量与复制计数，不实现解释器自己的内存分配器。实际运行记录中，1024 次连续追加复制了 1023 个元素；从 n=64 的满容量状态开始执行 20 对追加/删除，四分之一阈值复制 64 个，半满阈值复制 2560 个。这些数值是教学模型模拟，未测真实内存带宽或操作耗时。

本篇检查卡记录成本口径，完整输出在 examples/advanced-algorithms/results/foundations.json。运行输出检验模拟器与手算是否一致，一般摊还界仍由求和及势能证明承担。Python list 的具体增长策略不是这里声明的倍增策略，不能把模拟结果当作它的内部行为。