相关疑难解决方法(0)

是ArrayListjava中的数组还是列表？get操作的时间复杂度是什么,是O(n)或者O(1)？

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