выполнение динамического массива, увеличивающая константой вместо удвоения

Question

Я только что закончил экзамен, и один из вопроса было в итоге:

Учитывая пустой массив размера 1000, что амортизированная стоимость вставки n элементов в массив? Когда массив заполнен, вместо удвоения массива мы увеличиваем его на 1000 и копируем все элементы в новый массив, как и для динамических таблиц.

Я ответил O (n), но я не уверен в своем ответе. Я знаю, что амортизированное время выполнения динамической таблицы удвоения равно 2, но я не мог найти много информации о динамических таблицах, которые растут с постоянным размером.

Answer 1

Предположим, что начальный размер равен A, а приращение - тоже, и у нас есть N шагов. Для каждого шага требуется k * Размер элементарных операций для копирования элементов (и для очистки памяти, если необходимо).

Стоимость = k * (A + (A + A) + (A + 2A) + ... + (A + (N-1) A)) = k (A * N + A * (1 + 2 + 3 + ... + (N-1))) = k * (A * N + A * N * (N-1)/2) = O (N^2 * A) = O (N^2) (предполагая, что А является постоянным)

1 + 2 + 3 + ... + (N-1) является суммой arithmetic progression

PS Удвоение стоимости массива O (N)