Изменения

==Амортизационная стоимость каждой операции==

Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет 3. Докажем это используя метод предоплаты:

===Расширение массива===

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

===Сужение массива===

В случае с удаление ячейки будем действовать по схожей стратегии. 1 монетку на удаление, 1 монетку на элемент стоящий на позиции i-n/4, и 1 монетку на текущий элемент (точнее на его могилку после удаления). При это даже в самом худшем случае (только что расширились а потом n/4 раза удалили) у нас будет хватать денег на сужение.