用于向ArrayList中添加N个项目的Big-O运行时间

假设我将N个项目添加到Java中的ArrayList。这最糟糕的运行时间是什么？我知道它可能是O（N）来添加一个项目，因为数组可能需要调整大小。它不会调整N次，因为我添加了N个项目，甚至N个因子，因为每次调整大小时，（AFAIK）容量都会以某个因子增加。这意味着某种日志（N）调整大小。所以它似乎应该是O（N日志（N））插入N项，但我不完全确定这一点。我正在看的一门旧计算机科学考试的答案为O（N^2）。我错过了什么？用于向ArrayList中添加N个项目的Big-O运行时间

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

来源

2015-05-09 sudo

如果每个调整大小都将阵列容量增加相同的数量，则O（N^2）是成本界限。也许这就是考试问题所要求的。 –

其实，我发现考试题意味着插入任何位置。这包括前面，它需要把所有东西都转移下来。那是O（N^2）。 – sudo

的dynamic array被充分研究在计算机科学分期时间分析。简短的答案是，当从空的动态数组开始并添加元素时，总时间为O（N）。

你是正确的，将单个项目有Ø（ñ）时，必须进行调整大小，而Ø最坏情况下的时间（登录ñ）调整发生。

但是，当我们加起来这些调整操作，一共是唯一Ø（ñ），这是非常好的。下面是一个例子来说明比例因子是2（而不是ArrayList的比例因子3/2）：

N = 64：调整为1,2,4,8,16,32,64。总计操作= 127（大约2 N）。

来源

2015-05-09 18:36:08 Nayuki

不应该执行O（N）操作log（N）次导致O（N log（N）），就像添加到TreeMap一样？我知道将N项添加到一棵平衡树（而不是真正地细细研究）被认为是O（N log N）。 – sudo

从技术上说是的，但是N log N是*悲观*分析。 O（N）是紧密的分析。 – Nayuki

关键在于* N *在每个调整大小时都不相同，并将它们相加得到大约2 * N *。 – Nayuki

用于向ArrayList中添加N个项目的Big-O运行时间

回答

相关问题