数组列表成本 [英] Cost of array lists

问题描述

我知道，找到被附加到当尺寸加倍可以通过求和找到列表需要n个元素的门店数量Σ从n = 1至日志（2，N ）的2 ^ N = 2N-1 。结果
我的问题是如何使用的总和找到，而不是规模增加一倍时，名单不断增加每个它生长时间正好2000元公式？

I know that to find the number of stores needed for n elements to be appended to a list when the size is doubled can be found by the summation ∑ from n=1 to log(2,n) of 2^n = 2n-1.
My question is how I could use a summation to find a formula for when instead of doubling in size the list grows by exactly 2000 elements each time it grows?

推荐答案

所以，如果到2000元，那么阵列增加正大小的数组将增加地板（N / 2000）倍。如我们可以看到，它最近2000元素移动至多一次，下一个2000的槽（从端）移动两次，下一个2000的槽（从端）移动三次，依此类推。因此，我们有以下公式：

So, if array increases by 2000 elements, then n-sized array will increase floor(n/2000) times. As we may notice, last 2000 elements of it move at most once, next 2000-slot (from the end) moves twice, next 2000-slot (from the end) moves three times, and so on. So we have this formula:

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

这篇关于数组列表成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！