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