问动态数组中的移动数
EN

Stack Overflow用户

提问于 2013-07-04 16:54:28

回答 1查看 146关注 0票数 4

动态数组是一个将其大小加倍的数组，当将一个元素添加到已满的数组中时，将现有元素复制到新的place more details here中。很明显，将存在批量复制操作的ceil(log(n))。

在一本教科书中，我看到M的移动次数是这样计算的：

M=sum for {i=1} to {ceil(log(n))} of i*n/{2^i}的论点是“一半的元素移动一次，四分之一的元素移动两次”...

但我认为对于每个批量复制操作，复制/移动的元素数量实际上是n/2^i，因为每个批量操作都是通过达到和超过2^i th元素来触发的，所以移动的数量是

M=sum for {i=1} to {ceil(log(n))} of n/{2^i} (对于n=8，它似乎是正确的公式)。

在另一场争论中，谁是对的，什么是错的？

回答已采纳

发布于 2013-07-04 17:48:18

这两个版本都是O(n)，所以没有太大的区别。

教科书版本将每个元素的初始写入计数为移动操作，但不考虑第一个元素，这将移动ceil(log(n))时间。除此之外，它们是等价的，即

(sum for {i=1} to {ceil(log(n))} of i*n/{2^i}) - (n - 1) + ceil(log(n))
  == sum for {i=1} to {ceil(log(n))} of n/{2^i}

当n是2的幂时。当n不是2的幂时，两者的关断程度不同。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/17465984

复制

相似问题

问动态数组中的移动数EN