为什么动态数组总是翻倍的2倍？

我想知道如何决定动态数组调整大小的大小？在维基百科和其他地方，我总是看到元素数量增加了2倍？为什么2？为什么不是3？如何决定这个因素？如果它依赖于语言，我想知道这是Java的。为什么动态数组总是翻倍的2倍？

2010-03-30 Phoenix

因为根据定义，倍增总是2倍。如果你想增加3倍，你会增加3倍。 – 2010-04-01 21:53:21

实际上，在Java的ArrayList中的公式计算新的能力后调整大小为：

newCapacity = (oldCapacity * 3)/2 + 1;

这roughtly意味着1.5的因素。

关于这个数字的原因我不知道，但我希望有人做了统计分析，发现这是空间和计算开销之间的良好折衷。

来源

2010-03-30 14:06:49

@Andrea：即使在SO上也有一些不错的图表：http://stackoverflow.com/questions/1424826/why-is-vector-array-doubled/1426065#1426065 – 2010-04-01 20:50:23

Wikipedia从引用：

作为n个元素被插入，能力形成几何级数。以任何常数比例扩展数组可确保插入n个元素总共需要O（n）个时间，这意味着每个插入需要分摊不变的时间。这个比例a的值导致时间 - 空间折衷：每个插入操作的平均时间约为a /（a-1），而浪费的单元格的数目受（a-1）n限制。 a的选择取决于库或应用程序：a = 3/2 1和a = 2 [需要的引用]是常用的。

显然它似乎是CPU时间和内存浪费之间的一个很好的折衷。我猜“最好”的价值取决于你的应用程序的功能。

来源

2010-03-30 14:07:50 ereOn

关于分期偿还时间的关键是关键。谷歌“摊销分析”，并找到像http://www.cs.cornell.edu/Courses/cs312/2008sp/lectures/lec20.html – Matt 2010-04-01 21:05:42

你会浪费比实际使用的空间更多的空间吗？
如果不是，该因子应该小于或等于2.
如果您希望它是一个整数，所以使用起来很简单，只有一个选择。

来源

2010-04-01 20:48:58

为什么动态数组总是翻倍的2倍？

回答

相关问题