为什么动态数组在空间不足时会特别增大一倍？

Question

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

Answer 1

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

\n\n

\n
1 + m + m ² + ... + m ^{1+log _m n}。
\n

\n\n

要了解其原因，请注意（如果数组从大小 1 开始），则数组将以大小 1、m、m ²、... 增长，直到达到大小 n。最后一个增长步骤发生在 m ^{k = n 时，即 k = log}_m n时发生。考虑到超过 n 的另一增长步骤，此处的 +1 就得到了。

\n\n

上述总和是几何级数的总和，总和为

\n\n

\n
(m ^{2 + log _m n} - 1) / (m - 1)
\n\n
= (m ² n - 1)/ (m - 1)
\n\n
≤ n·(m ² / (m - 1))
\n

\n\n

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

\n\n

选择 m = 2 给出的领先系数为 4，这是相当低的。选择 1.5 给出的领先系数为 4.5。那\xe2\x80\x99 更高，但幅度不大。然而，选择 1.5 还有一些其他优点：

\n\n

如果我们继续增长数组，分配的数组永远不会比之前大 50%。与加倍相比，这减少了数据结构的开销。
如果我们需要增长数组，则先前数组的大小总和超过新数组的大小（检查这一点 - 两个 don\xe2\x80\x99t 的幂可以做到这一点）。这使得内存分配器更有可能从旧的废弃数组中回收空间以适应新数组。
乘以 1.5 可以通过计算来完成size + (size >> 1)，与乘法相比，这在处理器上极其便宜。

\n\n

希望这可以帮助！

\n