为什么ArrayList add()和add(int index,E)复杂度是分摊的常量时间？为什么O(1)for add(),O(n)for add(int index,E)？

Question

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

为什么O(1)用于单个add()操作,O(n)用于单个add(int index,E)操作,O(n)用于添加n个元素(n add操作)使用任何(任何)add方法？假设我们使用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)是"插入操作"？然后完全清楚!

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

什么是算法的摊销分析？

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

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

将O添加到不同的例程时

Answer 1

在Oracle术语(暗示默示)和谈论List

• " add method "(同义词 - " append method ")总是意味着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)[grow + insert],但2*O(n)与O(n)相同.