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

Question

动态数组是一个大小加倍的数组，当一个元素被添加到一个已经满的数组时，将现有元素复制到一个新的位置 more details here .很明显会有ceil(log(n))批量复制操作。

我在教科书中看到过 Action 次数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}

当n是 2 的幂。当 n 时两者相差不同的数量不是 2 的幂。