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

问题描述

我知道要找到当大小加倍时将 n 个元素附加到列表所需的存储数可以通过求和 ∑ from n=1 to log(2,n) of 2 找到^n = 2n-1.
我的问题是我如何使用求和来找到一个公式，而不是每次增长时列表的大小增加一倍?

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 大小的数组将增加 floor(n/2000) 倍.我们可能会注意到，它的最后 2000 个元素最多移动一次，下一个 2000 槽(从末尾)移动两次，下一个 2000 槽(从末尾开始)移动 3 次，依此类推.所以我们有这个公式:

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屋！