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

Question

为什么ArrayList的add（）和add（int index，E）复杂度要按固定时间摊销？

为什么不对单个add（）操作使用O（1），对单个add（int索引，E）操作使用O（n），而对于使用任一（任何）添加方法添加n个元素（n个添加操作）的O（n）呢？假设我们很少使用add（int
index，E）添加到数组末尾？

数组（和ArrayList）的操作复杂度已经不是n个元素了：

1. add（）-O（1）？
2. add（int index，E）-O（n）？

如果我们插入一百万次，则平均值1和2不能为O（1），对吗？

为什么甲骨文说

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

我认为add（）的复杂度为O（1），add（int index，E）的复杂度为O（n）。

这是否意味着“ n个操作的积分复杂度”（每个操作的复杂度为O（1））可以说n * O（1）= O（n）。我想念什么？

也许对于Oracle“添加操作”总是意味着仅add（）？而add（int，E）是“插入操作”吗？然后完全清除！

我有一个猜测，这与 渐进分析 和 摊销分析 之间的差异有关，但我无法掌握到最后。

什么是算法的摊销分析？

Answer 1

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

• “ 添加方法 ”（同义词-“ 附加方法 ”）始终表示boolean add(E)
• “ 插入方法 ”总是意味着boolean add(int index, E)

当Oracle写的时候

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

它的意思是：

单个boolean add(E)操作的复杂度以O（1）摊销。

它不能只是（总是）渐近的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)单个操作的复杂度始终为O（n）。如果触发增长，则为O（n）+ O（n）[增长+插入]，但2 * O（n）与O（n）相同。