arrays - 向扩展数组添加 1 个元素的最坏情况时间

Question

假设我们有一个扩展数组，当我们尝试向它添加一些东西但它被填充时，它的大小翻了一番。

根据幻灯片底部“摊销：扩展向量” ，添加一个元素的最坏情况时间是 2N，而不是 N？为什么是这样？

我认为这将是 N，因为将 N 个元素复制到新的双倍大小的数组需要 N 时间。

例如，假设我只向大小为 4 的填充数组添加一个元素。它会像这样：

1. 制作大小为 8 的新数组（4 的两倍）。
2. 将原始数组的所有元素复制到新数组（复制 4 次）。
3. 将新数组的第 5 个元素设置为附加元素（复制 1 次）。

那么这将复制元素 5 次，即 N + 1，而不是 2N？

Answer 1

将元素添加到扩展数组所需的操作是 O(2N)，因为首先您需要遍历整个数组并使用 O(N) 检查空白空间。因为这是最坏的情况，所以没有任何内容，您必须创建一个新数组并使用 O(N) 将整个内容从第一个数组复制到新数组。两种操作结合​​在一起导致 O(2N)。

当您考虑数组长度时，长度实际上是为数组保留的大小，而不是内部元素的数量。这就是为什么如果你没有在任何地方保存元素的数量，你需要遍历整个数组以获得一个空白空间。我说的是“空白空间”，因为它没有说明只添加了元素，并且没有在数组中删除任何元素。