dynamic-arrays - 动态数组中的移动次数

Question

动态数组是一个大小翻倍的数组，当一个元素被添加到一个已经完整的数组中时，将现有元素复制到一个新的地方更多细节在这里。很明显会有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，这似乎是正确的公式）。

在另一个论点中谁是对的，什么是错的？

Answer 1

两个版本都是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}

whenn是 2 的幂。当不是 2 的幂时，两者的关闭量不同n。