java 为什么 ArrayList add() 和 add(int index, E) 复杂度是摊销常数时间？为什么不是 O(1) 用于 add()，O(n) 用于 add(int index, E)？

Why ArrayList add() and add(int index, E) complexity is amortized constant time? Why not O(1) for add(), O(n) for add(int index, E)?

提问by Code Complete

Why ArrayList add() and add(int index, E) complexity is amortized constant time?

为什么 ArrayList add() 和 add(int index, E) 复杂度是摊销常数时间？

Why not O(1) for single add() operation, O(n) for single add(int index, E) operation and O(n) for adding n elements (n add operations) using either (any) add method? Supposing we are using add(int index, E) to add to array end rarely?

为什么不是 O(1) 用于单个 add() 操作，O(n) 用于单个 add(int index, E) 操作和 O(n) 用于使用（任何）添加方法添加 n 个元素（n 个添加操作）？假设我们很少使用 add(int index, E) 添加到数组末尾？

Isn't one operation complexity of array (and ArrayList) already having n elements:

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

1. add() - O(1)?
2. add(int index, E) - O(n)?

1. 添加（） - O（1）？
2. 添加（整数索引，E） - O（n）？

If we make a million insertions, the average of 1 and 2 cannot be O(1), right?

如果我们进行一百万次插入，1 和 2 的平均值不可能是 O(1)，对吗？

Why Oracle says

为什么甲骨文说

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.

add 操作以分摊常数 time运行，即添加 n 个元素需要 O(n) 时间。

I thought complexity is O(1) for add() and O(n) for add(int index, E).

我认为 add() 的复杂度是 O(1)，add(int index, E) 的复杂度是 O(n)。

Does it means that "integral complexity of n operations" (each operation of complexity O(1)) is so to speak n*O(1) = O(n). What am I missing?

这是否意味着“n 个操作的整体复杂度”（每个复杂度为 O(1) 的操作）可以说是 n*O(1) = O(n)。我错过了什么？

Maybe for Oracle "add operation" always means only add()? And add(int, E) is "insertion operation"? Then totally clear!

也许对于Oracle“添加操作”总是意味着只添加（）？而 add(int, E) 是“插入操作”？然后就彻底清楚了！

I have a guess, it has to do with difference between asymptotic analysisand amortized analysis, but I cannot grasp it to the end.

我有一个猜测，它与渐近分析和摊销分析之间的区别有关，但我无法将其掌握到底。

What is amortized analysis of algorithms?

什么是算法的摊销分析？

Why the time complexity of an array insertion is O(n) and not O(n+1)?

为什么数组插入的时间复杂度是 O(n) 而不是 O(n+1)？

More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?(not quite clear)

更适合说 Amortized O(1) vs O(n) 插入未排序的动态数组？（不太清楚）

Big O when adding together different routines

将不同的例程加在一起时的大 O

回答by Code Complete

In Oracle terms (which are implied tacitly) and speaking about List

在 Oracle 术语中（默认情况下）并谈论 List

• "add method" (synonym - "append method") always means boolean add(E)
• "insert method" always means boolean add(int index, E)

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

When Oracle writes

当 Oracle 写

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.

add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。

it means:

它的意思是：

Complexity of a single boolean add(E)operation is amortized O(1).

单个boolean add(E)操作的复杂度分摊为 O(1)。

It cannot be just O(1) asymptotic (always) because rarely we need to grow array capacity. This single add operation which is in fact a "create new bigger array, copy old array into it, and then add one element to the end" operation is O(n) asymptotic complexity, because copying the array when increasing List capacity is O(n), complexity of growing plus addding is O(n) [calculated as O(n) + O(1) = O(n)]. Without this capacity growing operation, add complexity would have been O(1), element is always added (appended) to the end of array (max index). If we "added" (= inserted) not to array end, we would need to move rightmost elements (with bigger indexes), and complexity for single such operation would have been O(n).

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

Now, for a single add operation asymptotic complexity is O(1) for add-without-increasing-capacity and O(n) for add-with-increasing-capacity (which happens very rare).

现在，对于单个添加操作，渐近复杂度对于不增加容量的添加是 O(1)，对于增加容量的添加是 O(n)（这种情况非常罕见）。

Amortized complexity of a single add operation is O(1). It reflects the fact that rare O(n) grow-and-add operations get "diluted" with much more numerous O(1) add-without-grow ones, so "on the average" single operation is O(1).

单个添加操作的摊销复杂度为 O(1)。它反映了一个事实，即罕见的 O(n) 增长和添加操作被更多的 O(1) 加而不增长操作“稀释”，因此“平均”单个操作是 O(1)。

"Asymptotic complexity" of n add operations is O(n). But here we speak about complexity of n operations, not complexity of one operation. It is not a strict way to put it like this ("Asymptotic complexity"), but anyway. Amortized complexity of n operations is even less sense.

n 个加法运算的“渐近复杂度”是 O(n)。但这里我们谈论的是 n 个操作的复杂度，而不是一个操作的复杂度。像这样说（“渐近复杂性”）并不是一种严格的方式，但无论如何。n 个操作的摊销复杂度更没有意义。

Finally, boolean add(int index, E)single operation complexity is always O(n). If it triggers grows, it is O(n) + O(n) [grow + insert], but 2*O(n) is same as O(n).

最后，boolean add(int index, E)单个操作的复杂度总是 O(n)。如果触发增长，则为 O(n) + O(n) [增长 + 插入]，但 2*O(n) 与 O(n) 相同。