java - 数组列表的成本

Question

我知道，要找到当大小加倍时，将 n 个元素追加到列表中所需的存储数量，可以通过从 n=1 到 log(2,n) of 2 的求和来找到 Σ ^n = 2n-1。
我的问题是，如何使用求和来找到一个公式，用于计算列表每次增长时恰好增长 2000 个元素，而不是使其大小加倍？

Answer 1

因此，如果数组增加 2000 个元素，则 n 大小的数组将增加 floor(n/2000) 倍。我们可能会注意到，它的最后 2000 个元素最多移动一次，下一个 2000 个槽(从末尾开始)移动两次，下一个 2000 个槽(从末尾开始)移动 3 次，依此类推。所以我们有这个公式:

∑ 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)