由一个固定不变每次成长动态数组效率？ [英] Efficiency of growing a dynamic array by a fixed constant each time?

问题描述

因此​​，当一个动态阵列的大小，每次添加的元素时间加倍，我明白扩大的时间复杂度如何为O（n）n是元素。怎么样，如果阵列复制并转移到一个新的数组，它是只有1规模更大的时候才满了吗？ （而不是增加一倍），当我们被一些常数C调整，它的时间复杂度始终为O（n）？

So when a dynamic array is doubled in size each time an element is added, I understand how the time complexity for expanding is O(n) n being the elements. What about if the the array is copied and moved to a new array that is only 1 size bigger when it is full? (instead of doubling) When we resize by some constant C, it the time complexity always O(n)?

推荐答案

如果您通过一些固定的常数C增长，那么没有，运行时不会为O（n）。相反，它会与西塔;（正 ² ）

If you grow by some fixed constant C, then no, the runtime will not be O(n). Instead, it will be Θ(n²).

要看到这一点，想想如果你可做C连续的操作顺序会发生什么。这些业务，C - 其中1需要时间O（1），因为空间已经存在。最近的操作将需要时间为O（n），因为它需要重新分配阵列，增加空间，并复制所做的一切。因此，C任何操作序列将需要时间为O（n + C）。

To see this, think about what happens if you do a sequence of C consecutive operations. Of those operations, C - 1 of them will take time O(1) because space already exists. The last operation will take time O(n) because it needs to reallocate the array, add space, and copy everything over. Therefore, any sequence of C operations will take time O(n + c).

所以，现在考虑，如果你执行n个操作的顺序会发生什么。打破这些操作成C尺寸的块;有将为n其中/℃。执行这些操作所需的总工作将

So now consider what happens if you perform a sequence of n operations. Break those operations up into blocks of size C; there will be n / C of them. The total work required to perform those operations will be

（C + C）+（2C + C）+（3C + C）+ ... +（N + C）

(c + c) + (2c + c) + (3c + c) + ... + (n + c)

= CN / C +（C + 2C + 3C + ... + NC / C）

= cn / c + (c + 2c + 3c + ... + nc / c)

= N + C（1 + 2 + 3 + ... + N / C）

= n + c(1 + 2 + 3 + ... + n / c)

= N + C（N / C）（N / C + 1）/ 2

= n + c(n/c)(n/c + 1)/2

= N + N（N / C + 1）/ 2

= n + n(n/c + 1)/2

= N + N ² / C + N / 2

= n + n² / c + n / 2

=西塔（N ² ）

此对比与数学，当你时，你需要更多的空间加倍数组大小为：所做的总功为

Contrast this with the math for when you double the array size whenever you need more space: the total work done is

1 + 2 + 4 + 8 + 16 + 32 + ... + N

1 + 2 + 4 + 8 + 16 + 32 + ... + n

= 1 + 2 + 4 + 8 + ... + 2 ^日志N

= 1 + 2 + 4 + 8 + ... + 2^{log n}

= 2 ^{日志N + 1} - 1

= 2^{log n + 1} - 1

= 2 - 1

= 2n - 1

=西塔（N）

希望这有助于！

这篇关于由一个固定不变每次成长动态数组效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！