Время выполнения динамического массива, которое увеличивается на константу вместо удвоения

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

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

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


data-structures dynamic-tables
person user1320353    schedule 17.04.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

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

Стоимость = 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) (при условии, что A постоянна)

1 + 2 + 3 +... + (N-1) — это сумма арифметической прогрессии

P.S. Удвоение массива стоит O(N)

person MBo    schedule 17.04.2012
comment
Вы имеете в виду: k * (A + (A+A) + (A+2A) + ... + (A+(N-1)*A)) вместо: k * (A + (A+A) + (A+2A) + (A+(N-1)*A)) так как в середине может быть больше терминов? Я дошел до этого момента, но не смог его упростить. Не могли бы вы немного объяснить, как вы упростили его до: k * (AN + AN*(N-1)/2)? - person user1320353; 17.04.2012
comment
Да, конечно пропустил..., поправил и добавил пару слов - person MBo; 17.04.2012
comment
Нет, если приращение = n, то Cost = AN + nN*(N-1)/2 = O(N^2) асимптотически - person MBo; 17.04.2012
comment
разве N не количество раз растет ваш массив? В моем случае я вставляю n элементов, и мы увеличиваем каждые 1000 элементов, так что не должно ли N = n/1000? - person user1320353; 17.04.2012
comment
Да, N - это количество раз, когда ваш массив растет. Если вы вставляете n элементов, то мы также увеличиваем каждые n элементов. N не зависит от n. - person MBo; 17.04.2012
comment
Если все требуется хранить в одном линейном массиве, добавление элементов по частям приводит к производительности O(N^2) при добавлении большого количества элементов N. Если разрешено использовать вложенные массивы, меньшие расширения создают меньше проблем. (если глубина вложенности увеличивается с увеличением N, все операции требуют затрат на единицу в размере O(lgN), но это время является абсолютным, а не амортизируемым). - person supercat; 05.03.2015