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

问题描述

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

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

为什么不是 O(1) 用于单个 add() 操作，O(n) 用于单个 add(int index, E) 操作和 O(n) 用于添加 n 个元素(n 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?

不是已经有 n 个元素的数组(和 ArrayList)的一种操作复杂度:

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

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

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

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

甲骨文为什么这么说

加法运算在摊销常数时间内运行，即加n元素需要 O(n) 时间.

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

这是否意味着n 个操作的整体复杂度"(每个操作的复杂度为 O(1))可以说是 n*O(1) = 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?

也许对于 Oracle 来说，添加操作"总是意味着只有 add()?而 add(int, E) 是插入操作"?然后就完全清楚了！

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

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

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

什么是算法的摊销分析?

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

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

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

推荐答案

在 Oracle 术语中(默认情况下)并谈论 List

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

• "add method" (同义词 - "append method") 总是表示 boolean add(E)
• 插入方法"总是表示boolean add(int index, E)

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

Oracle 写入时

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

意思是:

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

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

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

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)(这种情况非常罕见).

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) 增长和添加操作被更多的 O(1) 加而不增长操作稀释"，因此平均"单个操作是 O(1).

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).

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

"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.

最后，boolean add(int index, E) 单次操作的复杂度总是 O(n).如果触发grow，就是O(n)+O(n)[grow+insert]，但是2*O(n)和O(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).

这篇关于为什么 ArrayList add() 和 add(int index, E) 复杂度是摊销常数时间?为什么不是 O(1) 用于 add()，O(n) 用于 add(int index, E)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！