基于势能法证明扩容数组插入与删除的均摊时间为O(1)

问题定义 #

先明确通用参数规则：

• 设数组当前容量为M，元素个数为n
• 扩容触发条件：当n = M时，将容量扩容至X*M（X>1）
• 缩容触发条件：当n ≤ t*M时，将容量缩容至Y*M（0 < t < Y < 1）
• 目标：构造基于X、Y、t的通用势能函数，证明插入、删除操作的均摊时间复杂度为O(1)

势能函数构造核心思路 #

势能函数的本质是让操作的实际耗时与势能变化的总和保持有界，即每次操作的均摊时间（实际时间+势能变化）为常数。针对动态数组场景，势能需关联n与M的比例关系，通过分段设计覆盖扩容、缩容、平稳操作三个阶段。

通用势能函数形式 #

存在如下可参数化的势能函数：

Φ(M, n) = 
  k * (n - c*M) ，当 n ≥ c*M
  k * (c*M - n) ，当 n ≤ d*M
  0 ，当 d*M < n < c*M

其中：

• c取Y（缩容后的容量比例），d取t（缩容触发阈值比例）
• k为系数，需根据X、Y、t调整，以抵消扩容/缩容的批量复制耗时

具体场景验证（X=1.5，Y=0.75，t=0.5） #

针对你提到的扩容1.5倍、缩容至0.75倍（元素为容量一半时触发）的场景，可构造如下势能函数：

Φ(M, n) = 
  (8/3)*(n - 0.75M) ，当 n ≥ 0.75M
  2*(0.75M - n) ，当 n ≤ 0.5M
  0 ，当 0.5M < n < 0.75M

插入触发扩容的均摊时间验证

• 扩容前：n=M，势能为(8/3)*(M - 0.75M) = (8/3)*0.25M = (2/3)M
• 扩容后：容量变为1.5M，n=M，此时M < 0.75*1.5M = 1.125M，势能为0
• 势能变化：0 - (2/3)M = -(2/3)M
• 实际耗时：复制M个元素，耗时M
• 均摊时间：M + (-(2/3)M) + O(1) = O(1)（O(1)为插入基础操作耗时）

删除触发缩容的均摊时间验证

• 缩容前：n=0.5M，势能为2*(0.75M - 0.5M) = 0.5M
• 缩容后：容量变为0.75M，n=0.5M，此时0.5M > 0.5*0.75M = 0.375M且0.5M < 0.75*0.75M = 0.5625M，势能为0
• 势能变化：0 - 0.5M = -0.5M
• 实际耗时：复制0.5M个元素，耗时0.5M
• 均摊时间：0.5M + (-0.5M) + O(1) = O(1)（O(1)为删除基础操作耗时）

通用函数的存在性结论 #

对于任意满足1<X、0<t<Y<1的参数，均存在可参数化的势能函数：
通过调整系数k = 1/(Y(X-1))，可确保扩容时的势能变化抵消批量复制的大部分耗时；通过设置缩容阶段的势能系数为k' = t/(Y - t)，可确保缩容时的势能变化抵消批量复制耗时。最终所有操作的均摊时间均为O(1)。

内容的提问来源于stack exchange，提问作者s.m