爲什麼動態數組總是翻倍的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倍？

回答

相關問題