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

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^{对数 n + 1} - 1

= 2n - 1

= Θ(n)

---

^{从 SO 文档移植。}

2 的幂和 — 1 + 2 + 4 + 8 + 16 + ...</h3>

总和

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

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