algorithm - 为什么动态数组在空间不足时会特别加倍？

Question

我是摊销分析的新手。我注意到动态数组的一个常见做法是在空间不足时将其大小加倍。我们选择将尺寸加倍是否有特定原因？为什么不是三倍或四倍？使用摊销分析选择加倍是否有具体解释？还是选择是随意的？

Answer 1

通过按任何常数因子缩放来增加数组大小足以使运行时间达到 O(n)。要看到这一点，请注意，如果最终的数组大小以 n 结尾，并且我们在每一步中缩放 m 倍，那么增长数组的总工作量将是

1 + m + m² + ... + m^{1+log_m n}.

要了解这是为什么，请注意(如果数组从大小 1 开始)然后数组将以大小 1、m、m²、...增长，直到达到大小 n .最后一个增长步骤发生在 m^k = n 时，这发生在 k = log_m n 时。此处的 +1 考虑了一个超过 n 的增长步骤。

上面的和是一个几何级数的和，求和为

(m^{2 + log_mn} - 1) / (m - 1)

= (m²n - 1)/ (m - 1)

≤ n · (m² / (m - 1))

所以基本上任何大于 1 的指数都有效，但主要系数取决于我们选择的 m。对于大的 m，这个系数大约等于 m，我们最终会浪费大量的精力和空间来增长数组。如果 m 越来越接近 1，则分母会变得越来越大，并且越来越令人担忧。

选择 m = 2 给出的前导系数为 4，这是非常低的。选择 1.5 给出了 4.5 的领先系数。那更高，但不是很多。然而，选择 1.5 有一些其他的优势:

• 分配的数组，如果我们继续增长数组，绝不会比之前的数组大 50% 以上。与加倍相比，这减少了数据结构的开销。
• 如果我们需要扩大数组，之前数组的大小之和超过了新数组的大小(检查这个 - 2 的幂不这样做)。这使得内存分配器更有可能从旧的废弃数组中回收空间以适应新数组。
• 乘以 1.5 可以通过计算 size + (size >> 1) 来完成，与乘法相比，这在处理器上非常便宜。

希望这对您有所帮助!