Итак, я написал функцию 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;
}
Короткий ответ: по мере увеличения хранилища копия занимает в 4 раза больше времени, но бывает только 1/4го так часто. 4 и 1/4го отмените, так что вы получите (амортизированное) постоянное время.
Игнорируя точный коэффициент, который вы выбрали, в долгосрочной перспективе вы получите O (N * 1 / N) = O (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)
,