java - 用于将 N 项添加到 ArrayList 的 Big-O 运行时

Question

假设我在 Java 中将 N 个项目添加到 ArrayList。最坏情况下的运行时间是多少？我知道添加单个项目可能是 O(N)，因为数组可能需要调整大小。它不会在我添加 N 项时调整大小 N 次，甚至不会调整 N 倍，因为(据我所知)每次调整大小时，ArrayList 的容量都会增加一些因素。这将意味着某种 log(N) 数量的调整大小。所以看起来应该是 O(N log(N)) 来插入 N 项，但我对此并不完全确定。我正在查看的旧计算机科学考试的答案为 O(N^2)。我错过了什么吗？

int newCapacity = (oldCapacity * 3)/2 + 1; ( from this answer )

Answer 1

dynamic array在计算机科学中对摊销时间分析进行了深入研究。简短的回答是，当从一个空的动态数组开始并添加 N 个元素时，总时间是 O(N)。

您是正确的，当必须执行调整大小时，添加单个项目的最坏情况时间为 O(N)，并且 O(log N) 次调整发生。

但是当我们将这些调整大小的操作加起来时，总数只有O(N)，这是非常好的。这里有一个例子来说明当缩放因子是 2 时(而不是 ArrayList 的缩放因子 3/2):

N = 64:将大小调整为 1、2、4、8、16、32、64。总操作数 = 127(大约 2N)。