Число перемещений в динамическом массиве

Question

Динамический массив - это массив, удваивающий его размер, когда элемент добавляется в уже полный массив, копируя существующие элементы в новое место 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 это правильная формула).

Кто прав, а что нет в другом аргументе?

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.