1632
правки
Изменения
м
rollbackEdits.php mass rollback
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>.
=== add(x) ===
:Добавление в массив элемента <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в во вдвое больший массив {{---}} <tex>O(n)</tex> (<tex>n</tex> {{---}} размер массива).
=== del() ===
:Удаляет последний элемент массива. В случае, если количество элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> {{---}} константы, зависящие от реализации). Время выполнения операции в худшем случае {{---}} <tex>O(n)</tex>.
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''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 \bmod \dfrac{n}{4}</tex>. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\dfrac{n}{4}</tex> удалили) у каждого элемента из первых <tex>\dfrac{n}{4}</tex> будет по монете и на удаление надо будет потратить только <tex>1</tex> монету.
=== Метод потенциалов ===
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c
\end{cases}</tex> , где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.
==== Стоимость операции '''add(x)''' ====
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s3s-\frac{3}{2}c= 3 + \frac{s}{c}c3c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex>
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex>
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex>
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex>
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=30</tex>
Средняя стоимость операции {{---}} <tex>2</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.
