为何Python列表append操作摊还成本为O(1)？求非翻倍扩容的数学分析

核心结论 #

只要动态数组的扩容策略满足每次扩容后的容量是当前容量的常数倍（大于1），无论倍数是1.125、1.5还是2，append操作的摊还复杂度都能保证为O(1)。Python的ceil(9n/8+6)本质是一种带偏移的几何增长策略，依然符合这个核心条件。

数学分析（聚合分析法） #

我们通过聚合分析（Aggregate Analysis）推导：

1. 定义变量

设：

• 第k次扩容前的数组容量为C_k（此时数组已满，元素数等于C_k）
• 扩容后的新容量为C_{k+1} = ceil(9*C_k/8 + 6)
• 两次扩容之间，可执行M_k = C_{k+1} - C_k次无需扩容的append操作，每次操作耗时O(1)
• 每次扩容需要移动C_k个元素，耗时O(C_k)

2. 关键观察：容量的几何增长性

当C_k足够大时（比如C_k > 48），9*C_k/8 + 6 < 9*C_k/8 + C_k/8 = 1.25*C_k，同时ceil(9*C_k/8 +6) ≥ 9*C_k/8 = 1.125*C_k。这意味着：

扩容后的容量至少是当前容量的1.125倍，属于几何级数增长，而非线性增长。

3. 总操作耗时计算

假设我们执行了N次append操作，对应经历了m次扩容：

• 所有append操作的基础耗时：O(N)
• 所有扩容的移动总耗时：S = C_0 + C_1 + ... + C_{m-1}（C_0是初始容量）

由于C_k是几何级数增长，公比r=9/8>1，等比数列求和公式可得：

S = C_0 * (r^m - 1) / (r - 1)

而N ≤ C_m（第m次扩容后容量为C_m，足以容纳N个元素），且C_m ≥ C_0 * r^m，因此r^m ≤ C_m / C_0，代入求和公式：

S ≤ C_0 * (C_m/C_0 - 1) / (r - 1) = (C_m - C_0) / (r - 1)

因为r-1=1/8，所以S ≤ 8*(C_m - C_0) = O(C_m) = O(N)（因为C_m ≥ N）。

4. 摊还复杂度推导

总耗时为基础append耗时加扩容移动耗时：O(N) + O(N) = O(N)。
将总耗时均分到N次append操作上，每次操作的摊还耗时为O(N)/N = O(1)。

与线性扩容的本质区别 #

如果采用固定增量扩容（比如每次加10个槽位），容量是线性增长的，此时扩容移动总耗时为：

S = C_0 + (C_0+10) + (C_0+20) + ... ≈ O(N²)

总耗时变为O(N²)，摊还复杂度为O(N)，这才是低效的根源。

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