为什么动态数组在用完空间的时候会特别大一倍？

Question

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

Answer 1

通过按任意常数因子缩放来增长数组大小，就足以使运行时间达到O(n)。要了解这一点，请注意，如果最终的数组大小为n，而我们在每一步上都按m的系数缩放，那么增长数组所做的总工作将是

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

要知道为什么会这样，请注意（如果数组从大小为1开始），那么数组将以1，m，m的大小增长。²最后一个成长步骤发生在m^k ＝n，当k＝log_m n. 考虑到再增加一个增长步骤以超额完成n的因素，这里的+1就解释了。

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

(m^2+对数_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%以上。这与加倍相比，减少了数据结构的开销。
• 如果我们需要增长数组，之前数组的大小之和超过新数组的大小（检查一下--二的幂数不会这样做）。这使得内存分配器更有可能从旧的被丢弃的数组中回收空间来适应新数组。
• 乘以1.5，可以通过计算 size + (size >> 1)，与乘法器相比，在处理器上极为便宜。

希望这能帮到你!

Answer 2

你可能已经发现 在这个职位上，动态阵列的摊余复杂度为 O(1). 如果你看到分析，你会发现，如果你改变了 2 到 3 或 4 或甚至对任何其他常数（大于 1)数，甚至是小数。例如，在Microsoft Visual C++中，使用 1.5 作为生长因子 [1] (见所提供链接中的更多案例)。

因此： 2 在这里并不是一个特别的生长因子，其他因子也在使用。此外，如前所述 此处:

然而，许多教科书为了简化和分析的目的，使用a=2。