为什么ArrayList的add（）和add（int index，E）复杂度要按固定时间摊销？为什么不为add（）设置O（1），为add（intindex，E）设置O（n）？

用Oracle的术语（默示的）和谈论List

• “ 添加方法 ”（同义词-“ 附加方法 ”）始终表示

  boolean add(E)

• “ 插入方法 ”总是意味着

  boolean add(int index, E)

当Oracle写的时候

加法运算以固定的固定时间运行，也就是说，添加n个元素需要O（n）时间。

它的意思是：

单个

boolean add(E)

它不能只是（总是）渐近的O（1），因为很少需要增加阵列容量。实际上，此单个添加操作是“创建新的更大的数组，将旧的数组复制到其中，然后将一个元素添加到末尾”操作，其渐近复杂度为O（n），因为在增加List容量时复制数组为O（
n），增长加法的复杂度为O（n）[计算为O（n）+ O（1）=
O（n）]。如果没有这种容量增长操作，则添加复杂度将为O（1），元素总是添加（附加）到数组的末尾（最大索引）。如果我们不向数组末尾“添加”（=插入），则需要移动最右边的元素（具有更大的索引），并且单个此类操作的复杂度将为O（n）。

现在，对于单个加法运算，渐进复杂度为O（1）表示不增加容量，而O（n）表示不增加容量（这种情况很少发生）。

单个加法运算的摊余复杂度为O（1）。它反映了一个事实，即稀有的O（n）增长与添加操作会被大量的O（1）无增长操作“稀释”，因此“平均”的单个操作为O（1）。

n个加法运算的“渐近复杂度”为O（n）。但是在这里，我们谈论的是n个运算的复杂度，而不是一个运算的复杂度。这不是严格的表达方式（“渐进复杂性”），但无论如何。n次操作的摊销复杂度甚至没有意义。

最后，

boolean add(int index, E)