每次固定常数生成动态数组的效率？ [英] Efficiency of growing a dynamic array by a fixed constant each time?

问题描述

因此，当每次添加元素时，动态数组的大小加倍，我就明白了扩展的时间复杂度是O（n）n是元素。如果数组被复制并移动到一个只有1个大小的新数组，当它是满的？ （而不是加倍）当我们通过一些常量C调整大小时，它的时间复杂度总是O（n）？

解决方案

如果你增长一些固定常数C，然后不，运行时不会是O（n）。相反，它将是Θ（n ² ）。

要看到这一点，想想如果你连续执行一个C序列，会发生什么操作。在这些操作中，由于空间已经存在，C-1将需要时间O（1）。最后一个操作需要时间O（n），因为它需要重新分配数组，添加空间，并复制所有的东西。因此，任何C操作序列都需要时间O（n + c）。

因此，现在考虑如果执行n个操作的顺序会发生什么。将这些操作分解成大小为C的块;会有n / C的。执行这些操作所需的总体工作将是

（c + c）+（2c + c）+（3c + c）+ ... +（n + c）

= cn / c +（c + 2c + 3c + ... + nc / c）
$ b

= n + c（1 + 2 + 3 + ... + n / c）

= n + c （n / c）（n / c + 1）/ 2

= n + n（n / c + 1）/ 2

= n + n ² / c + n / 2

=&Theta n ² ）

与数学对比，当您需要更多空间时，双倍的数组大小：完成的工作是

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

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

= < class ='doc-link'href =http://stackoverflow.com/documentatio n / math / 3458 /计算机科学中的共同计算/ 11961 / sum-of-two-1-2-4-8-16＃t = 201702071620136584027> 2 ^{log n + 1} - 1

= 2n - 1

=Θ（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)?

解决方案

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

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

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)

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

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

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

= n + n(n/c + 1)/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 + ... + 2^{log n}

= 2^{log n + 1} - 1

= 2n - 1

= Θ(n)

Hope this helps!

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