Big-O运行时将N个项添加到ArrayList中

Question

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

int newCapacity = (oldCapacity * 3)/2 + 1;(从这个答案)

Answer 1

该动态数组被充分研究在计算机科学分期时间分析.简短的回答是,当从空动态数组开始并添加N个元素时,总时间为O(N).

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

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

N = 64:调整大小为1,2,4,8,16,32,64.总操作= 127(大约2 N).