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

Question

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

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

я) некоторая константа С

ii) н / 2

iii) п ^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 или более) имеет постоянную амортизированную стоимость.