Нахождение амортизированной временной сложности

Итак, я написал функцию push_back для векторного класса, и я сейчас пытаюсь выяснить сложность амортизированного времени. Я довольно плохо знаком с теоретической стороной программирования, так что, если кто-то сможет мне помочь, это будет потрясающе.

Это моя функция:

void Vector<T>::push_back(const T &e) {
if(vsize + 1 > capacity)
allocate_new();
array[vsize] = e;
vsize++;
}

а это мой allocate_new функция:

void Vector<T>::allocate_new() {
capacity = vsize * 4;
T* tmp = new T[capacity];

for(int i = 0; i < vsize; i++)
tmp[i] = array[i];

delete[] array;
array = tmp;
}

0

Решение

Короткий ответ: по мере увеличения хранилища копия занимает в 4 раза больше времени, но бывает только 1/4го так часто. 4 и 1/4го отмените, так что вы получите (амортизированное) постоянное время.

Игнорируя точный коэффициент, который вы выбрали, в долгосрочной перспективе вы получите O (N * 1 / N) = O (1) -> амортизированное постоянное время.

1

Другие решения

Когда вы вставляете N элементы в массиве, массив должен изменять размер при каждой степени 4. Количество времени, необходимое для изменения размера в размере 4^i является O(4^i), И точно так же, максимальное изменение размера выполняется в размере N, Итак, общая сумма взятия составляет:

T = 1 + 4 + 16 + ... + 4^x

где 4^x <= N, таким образом T=O(4^x)=O(N), Таким образом, среднее время для каждой операции вставки включено O(1),

1