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

Question

我知道将一个元素插入数组需要一个常数时间让我们说 c。

我尝试过的:

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

我想问的是big O of n还是o(1)

Answer 1

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

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

但是如果新的空间分配是一个大于原始空间的一个的常数因子(通常使用 2)，那么副本的成本会分摊，这样每次添加的平均时间就像你说的那样是常数，和 n 添加是 O(n)。

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

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

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