摊还分析证明ArrayList的add操作平均时间复杂度为O(1)：因1.5倍扩容使总复制次数小于2倍最终容量，n次添加总代价O(n)，均摊即O(1)；该策略在扩容频次与空间利用率间取得最优平衡。
ArrayList 的扩容操作看似昂贵，但通过摊还分析（Amortized Analysis）可以证明：对单个元素的 add 操作，其平均时间复杂度为 O(1)。这不是最坏情况的保证，而是多次操作整体成本被“均摊”后的结果。
为什么需要摊还分析？
因为扩容本身是 O(n) 操作——每次触发时，需创建新数组并复制全部已有元素。若每次都扩容，100 次添加可能引发数十次复制，总开销远超线性。但实际扩容并不频繁，且越往后间隔越长。摊还分析正是用来刻画这种“稀疏高成本 + 密集低成本”的整体行为。
关键扩容规律：1.5 倍增长
Java ArrayList 不是每次加 1 或翻倍，而是按公式计算新容量：
newCapacity = oldCapacity + (oldCapacity >> 1)，即 ×1.5（向下取整）。例如：
- 初始容量 10 → 扩容至 15
- 15 → 22（15 + 7）
- 22 → 33（22 + 11）
- 33 → 49（33 + 16）
该策略确保：从首次扩容起，每轮扩容后，数组至少还能容纳「当前已存元素数」一半的新元素，从而拉长两次扩容之间的插入次数。
摊还成本推导（势能法简述）
定义势能函数 Φ = 2 × size − capacity。
它反映“已用空间的冗余程度”：当 size 接近 capacity 时，Φ 趋近于 size；当 capacity 远大于 size 时，Φ 可能为负（但不影响分析）。
对一次 add 操作分析摊还代价：
摊还代价 = 实际代价 + ΔΦ
- 若不扩容：实际代价 = O(1)，size 增 1 → Φ 变化 ≤ +2 ⇒ 摊还代价 = O(1)
- 若扩容（设旧容量为 c，旧 size = c）：
– 实际代价 = O(c)（复制 c 个元素）
– 新 capacity = ⌊1.5c⌋，新 size = c+1 ⇒ 新 Φ ≈ 2(c+1) − 1.5c = 0.5c + 2
– 旧 Φ = 2c − c = c
– ΔΦ ≈ (0.5c + 2) − c = −0.5c + 2
– 摊还代价 ≈ c + (−0.5c + 2) = 0.5c + 2 = O(c)，但注意：这个 c 是「上一次扩容时的容量」，而它只在每约 log₁.₅ n 次 add 中出现一次
更直观的聚合分析：假设执行 n 次 add，初始容量为 10，最终容量为 C。由于每次扩容至少 ×1.5，总扩容次数最多为 log₁.₅(C/10) ≈ O(log n)。所有复制操作的总元素移动次数为：
10 + 15 + 22 + 33 + … + C 而最终 size = n，且 C
因此，n 次 add 的总代价 O(1)。
对比其他策略为何不优
固定增量（如每次 +10）：扩容太频繁，总复制量达 O(n²)；
严格倍增（×2）：空间浪费严重，最坏时一半空间闲置；
1.5 倍策略在理论与工程间取得平衡——既控制了扩容频次（O(log n) 次），又限制了空间冗余（峰值利用率 ≥ 2/3）。
