c - 向数组末尾插入 n 个元素的时间复杂度是多少？

我知道向数组中插入一个元素需要一个恒定的时间让我们说 c。

我试过的：

用于插入 n 个元素 time=c+c+c+.......n times =nc

我想问一下，它会是 n 的大 O 还是 o(1)。

标签： cdata-structures

是的，添加n元素需要 O(n) 时间，但添加单个项目不是 O(1)。它的摊销O(1)。

任何给定的添加都可能需要 O(n) 时间，因为当前数组的空间已被填满，因此必须将其复制到另一个更大的空间。

但是，如果新的空间分配是一个大于原始空间之一的常数因子（经常使用 2），那么复制成本会摊销，以便每次添加的平均时间如您所说是恒定的，并且n添加是 O(n)。

为了更清楚地说明这一点，请考虑因子为 2 且初始数组大小为 1 的情况。然后考虑复制成本以将数组从大小 1 增长到足以容纳任何 k>= 的 2^k+1 个元素0。这个大小是 2^(k+1)。总复制成本将包括所有复制到 2 倍大的步骤：

1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 = 2n - 1

等式是由于基本代数。结果是 O(n)。但是，最后一个副本本身有 n = 2^k 个元素，这也是 O(n)。