为什么ArrayList add（）和add（int index，E）复杂性是摊销常数时间？为什么不是 O（1）代表 add（），O（n）代表 add（int index， E）？

arrays time-complexity java arraylist

2022-09-02 01:10:27

为什么ArrayList add（）和add（int index，E）复杂性是摊销常数时间？

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

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

add（） - O（1）？
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（）？而 add（int， E）是“插入操作”吗？然后完全清除！

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

什么是算法的摊销分析？

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

更合适的说法是摊销 O（1）与 O（n）插入到未排序的动态数组中？（不太清楚）

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

答案 1

在Oracle术语中（隐含地暗示）并谈论列表

"add method“（同义词 - ”add method“）总是意味着boolean add(E)
"插入方法“始终意味着boolean add(int index, E)

当甲骨文写入时

添加操作在摊销常量时间内运行，即添加 n 个元素需要 O（n）时间。

这意味着：

单个操作的复杂性摊销为 O（1）。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个运算的摊销复杂度更不合理。

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

答案 2

为什么ArrayList add（）和add（int index，E）复杂性是摊销常数时间？为什么不是 O（1） 代表 add（），O（n） 代表 add（int index， E）？

为什么ArrayList add（）和add（int index，E）复杂性是摊销常数时间？为什么不是 O（1）代表 add（），O（n）代表 add（int index， E）？