按k+√k规则扩容的动态数组摊还分析上下界求解

前提定义 #

• 每次插入新元素的基础代价为1，直接写入数组空位
• 数组容量为k时如果被填满，触发扩容：新容量为newSize = k + √k，扩容代价为k（需拷贝全部k个原有元素到新数组）
• 初始数组容量为1，共执行n次连续插入操作，n足够大

总代价量级推导 #

总操作代价由两部分组成：n次插入的基础代价，加上所有扩容操作的拷贝代价。我们仅需要证明扩容总代价为Θ(n√n)，即可得到总代价为Θ(n√n)，单操作平摊代价为Θ(√n)。

连续扩容的递推关系 #

设第t次扩容前的数组容量为k_t，扩容规则可写为：
k_{t+1} - k_t = √k_t
我们可以将离散递推近似为连续微分（n足够大时误差可忽略），得到微分方程：
dk/dt = √k
分离变量积分：
∫ k^{-1/2} dk = ∫ dt
积分结果为 2√k = t + C，代入初始条件t=0时k=1，得常数C=2，因此当数组容量增长到k时，累计扩容次数t≈2(√k - 1)。

扩容总代价的积分估计 #

扩容总代价为所有扩容时的拷贝代价之和，即S=Σ_{t=0}^{T-1} k_t，其中T为完成n次插入的总扩容次数，最终数组容量k_T介于n和n+√n之间。
结合递推关系dt = dk/√k，可将求和转化为积分估计：
S ≈ ∫_{k=1}^{k=n} k * dt = ∫_{1}^n k*(dk/√k) = ∫_{1}^n √k dk = (2/3)k^{3/2}|_{1}n = Θ(n^{3/2}) = Θ(n√n)

紧上下界证明 #

• 下界：当n足够大时，扩容总代价S ≥ (2/3)(n^{3/2} - 1) = Ω(n√n)
• 上界：最终数组容量k_T ≤ n + √n，因此S ≤ (2/3)((n+√n)^{3/2} -1) ≤ 2n^{3/2} = O(n√n)
  因此扩容总代价为Θ(n√n)，加上n次插入的基础代价后总操作代价仍为Θ(n√n)，单操作平摊代价为Θ(√n)。

记账法验证 #

每次扩容后，数组有√k个空位，接下来的√k次插入不会触发扩容：

• 每次插入时，除支付1个币用于写入操作外，额外存储√k个币
• 连续√k次插入共存储√k * √k = k个币，刚好可以支付下次扩容时拷贝k个元素的代价
  由于数组最大容量不超过n+√n，因此每次存储的币数不超过√(n+√n)=O(√n)，对应单操作平摊代价为O(√n)，与推导结果一致。

内容的提问来源于stack exchange，提问作者Noy