每次以固定常数增长动态阵列的效率？

Question

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

Answer 1

如果你增长一些固定常数C,那么不,运行时不会是O(n).相反,它将是Θ(n ²).

要看到这一点,请考虑如果执行一系列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

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