arrays - 如果通过重复加倍完成，为什么调整数组大小操作的时间与 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 是数组“加倍”的计数。

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

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