arrays - 每次以固定常数增长动态数组的效率？

Question

因此，当每次添加元素时动态数组的大小加倍时，我理解扩展的时间复杂度是 O(n) n 作为元素。如果数组被复制并移动到一个新数组，当它已满时，它的大小只有 1 倍怎么办？ (而不是加倍)当我们通过某个常数 C 调整大小时，时间复杂度总是 O(n)？

Answer 1

如果你增加了一些固定的常数 C，那么不，运行时间不会是 O(n)。相反，它将是 Θ(n2)。

要看到这一点，请考虑如果您执行一系列 C 连续操作会发生什么。在这些操作中，C - 1 个将花费时间 O(1)，因为空间已经存在。最后一个操作将花费 O(n) 时间，因为它需要重新分配数组、添加空间并复制所有内容。因此，任何 C 操作序列都需要时间 O(n + c)。

所以现在考虑如果你执行 n 个操作的序列会发生什么。将这些操作分解成大小为 C 的块；将有 n/C 个。执行这些操作所需的总工作量将是

(c + c) + (2c + c) + (3c + c) + ... + (n + c)

= cn / c + (c + 2c + 3c + ... + nc / c)

= n + c(1 + 2 + 3 + ... + n / c)

= n + c(n/c)(n/c + 1)/2

= n + n(n/c + 1)/2

= n + n² / c + n / 2

= Θ(n²)

将此与在需要更多空间时将数组大小加倍时的数学进行对比:完成的总工作是

1 + 2 + 4 + 8 + 16 + 32 + ... + n

= 1 + 2 + 4 + 8 + ... + 2^{log n}

= 2^{log n + 1} - 1

= 2n - 1

= Θ(n)

从 SO 文档移植。

2 的幂和 - 1 + 2 + 4 + 8 + 16 + ...

总和

2⁰ + 2¹ + 2² + ... + 2^n-1

简化为 2n - 1。 这解释了为什么可以存储在无符号 32 位整数中的最大值是 232 - 1。