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

Question

У меня есть динамический массив, к которому я постоянно добавляю элементы.Приложение сложность O(1).Когда массив заполняется, я хотел бы увеличить массив и скопировать его, что представляет собой сложность O(n).

Теперь, предположим, я увеличиваю массив с разной скоростью, когда он заполняется.Эти ставки:

i) Некоторая константа C

ii) n / 2

iii) n ^ 2

Что такое амортизированное время выполнения в каждомиз этих сценариев?

Я считаю, что мне удалось решить дело i.Амортизированное время выполнения будет представлять собой общую стоимость операций, деленную на общее количество операций.В этом случае общая стоимость составляет C * O(1) + 1 * O(n), а общее количество операций - C.Таким образом, амортизированное время выполнения составляет O(n).

Однако я немного растерялся, анализируя два оставшихся случая.Мне кажется, что общее количество операций будет n/2 + 1 и n^2 + 1, соответственно, но я не совсем знаю, как рассчитать общую стоимость операций.

Кто-нибудь может привести меня на правильный путь?

Answer 1

Вы можете использовать анализ, аналогичный первому случаю.

ii.
(n/2 * O(1) + O(n)) / (n/2) = O(1) + O(n)/n = O(1)
iii.
(n^2 * O(1) + O(n)) / (n^2) = O(1) + O(n)/n^2 = O(1)

Этот ответ дает более подробное объяснение того, почему динамический массив имеет размеры, пропорциональные n(при условии, что он изменяет размер до n мощность 1 или больше) имеет постоянную амортизированную стоимость.