如果通过重复加倍来完成数组调整大小操作，为什么时间与 N 成正比？

Question

如果数组已满并且其大小增加 1 来插入新元素，则插入 N 个元素的时间可以计算为 1+2+ .. N = N^2/2。（声明长度为 size+1 的新数组并将元素复制到新数组）。

我无法理解如果我们不是将数组大小增加 1，而是声明一个长度为 2*size 的新数组，然后复制新数组中的元素，那么如何计算时间。

Answer 1

假设您有一个大小为 1 的数组，并且该数组每次变满时都会加倍。

现在，您将插入 2048 个项目：然后，当其长度变为 时，它将扩展并复制内容2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048。总共需要 4094 (~2n) 次操作。

此外，将n项目简单地插入到数组中也需要进行操作。

总之，它是O(n)线性的。

可以很容易地用带有系数r = 2和第一项的几何级数和公式来描述a1 = 2：

Sn = a1 * (r ^ n - 1) / (r - 1)
   = 2 * (2 ^ n - 1) / (2 - 1) 
   = 2 * 2 ^ n

其中n是数组“加倍”的计数。

由于加倍发生在 pow 为 2 的情况下，因此通常接近log2(n)。

2 * 2 ^ log2(n) = 2 * n，这意味着它始终是线性的。