相关疑难解决方法(0)

它与渐近分析有什么不同？你什么时候使用它,为什么？

我读过一些似乎写得很好的文章,比如:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我还是没有充分理解这些概念.

所以,有人可以为我简化吗？

为什么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添加到不同的例程时

因此,当每次添加元素时动态数组的大小加倍时,我理解扩展的时间复杂度是O(n)n是元素.如果将数组复制并移动到一个只有1个大小的新数组呢？(而不是加倍)当我们通过某个常数C调整大小时,时间复杂度总是为O(n)？