arrays - 为什么要双倍堆叠容量而不是仅仅增加固定数量？

Question

我正在使用堆栈的数组实现，如果堆栈已满而不是抛出错误，我会将数组大小加倍，复制元素，更改堆栈引用并将新元素添加到堆栈中。 (我正在跟着一本书自学这些东西)。

我不完全明白为什么要加倍，为什么不增加一个固定的数量，为什么不增加3倍。

我认为它与时间复杂度有关吗？

一个解释将不胜感激!

Answer 1

从理论上讲，您确实到达了不同的时间复杂度。如果增加一个常量大小，则将重新分配的数量(因此是 O(n) 个副本)除以一个常量，但您仍然会获得 O(n) 的追加时间复杂度。如果将它们加倍，则追加的时间复杂度更高(装甲化 O(1) IIRC)，并且由于您最多消耗两倍所需的内存，因此仍然获得相同的空间复杂度。

在实践中，它不那么严重，但仍然可行。副本很昂贵，而一点内存通常不会受到伤害。这是一种权衡，但您必须非常低内存才能选择另一种策略。通常，您事先不知道(或由于 API 限制而无法让堆栈知道)您实际需要多少空间。例如，如果你从一个元素开始构建一个 1024 个元素的堆栈，你会从 1024/K 开始(我可能会偏离一个)10 次重新分配——假设 K=3，那将是大约 34 倍许多重新分配，只是为了节省一点内存。

这同样适用于任何其他因素。 2 很好，因为你永远不会得到非整数大小，而且它仍然很小，将浪费的空间限制在 50%。其他因素可能会更好地为特定用例提供服务，但通常 ROI 太小，无法证明重新实现和优化某些库中已有的内容是合理的。