50
правок
Изменения
м
→Стоимость операции del(): неправильно была описана.
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex dpi=150>i</tex> и <tex dpi=150>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.
==== Стоимость операции del() ====
При каждой операции будем использовать три две монетки. Одну из них потратим на само удаление элемента, одну монету другую на элемент, стоящий на позиции <tex dpi=150>i-\fracbmod \dfrac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex dpi=150>\fracdfrac{n}{4}</tex> удалили) у нас каждого элемента из первых <tex>\dfrac{n}{4}</tex> будет хватать денег по монете и на копирование в новый массивудаление надо будет потратить только <tex>1</tex> монету.
=== Метод потенциалов ===
За потенциал примем число:
