315
правок
Изменения
→Стоимость операции add(x)
:Возвращает значение i-ой ячейки массива. Время выполнения — <tex>O(1)</tex>.
== Стоимость операции add(x) ==
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]Применим амортизационный анализ (конкретно — метод предоплаты) для того, чтобы доказать, что среднее время работы операции add(x) — <tex>O(1)</tex>.<br>
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили i-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — 3, и среднее время её работы — <tex>O(1)</tex>.
