數組列表的代價

Question

我知道，在大小加倍的情況下，可以通過求和∑ from n=1 to log(2,n) of 2^n = 2n-1找到n個元素附加到列表所需的存儲數量。
我的問題是我怎麼可以使用求和來找到什麼時候的公式，而不是大小增加一倍，每次增長的時候，列表的精確度會增加2000個元素？

Answer 1

所以，如果數組增加2000個元素，那麼n大小的數組將增加floor(n/2000)次。我們可能會注意到，它的最後2000個元素最多移動一次，下一個2000時隙（從末端）移動兩次，下一個2000時隙（從末端）移動三次，以此類推。所以我們有這個公式：

∑ i = 1 to floor(n/2000)[ i * 2000 ] = 

2000 * (∑ i = 1 to floor(n/2000) [ i ]) = 

2000 * (1 + 2 + 3 + .. + floor(n/2000)) = 

2000 * (floor(n/2000)*(1 + floor(n/2000))/2)