355
правок
Изменения
→Амортизационная стоимость каждой операции
== Амортизационная стоимость каждой операции ==
Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.=== Стоимость операции add(x) Метод предоплаты ======= Метод предоплаты Стоимость операции add(x) ====
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили i-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — <tex>3</tex>, и среднее время её работы — <tex>O(1)</tex>.
==== Стоимость операции del() ====При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.==== Метод потенциалов ====
За потенциал примем число:
<tex>\Phi(c, s) = \begin{cases} 2s - c , & \text{if } s\ge\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> - число элементов массива.
* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1) Массив -2c)-(2s-c) = 3 </tex>* <tex dpi=150>1>\frac{s}{c}\ge\frac{1}{2}</tex>, массив не расширяется: <tex> a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1+ (2(s + 1) - c)-(2s-c)=3</tex>* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s +1}{c}\ge\frac{1}{2}</tex>, массив не расширяется: <tex>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+s-\frac{3}{2}c= 3 + \frac{s}{c}c-\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> a_i = t_i + \Phi(2cc, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1) + ) - (\frac{1}{2 }c - s ) = 3 0</tex>
В итоге, средняя стоимость операции add(x) — <tex>3</tex>, а среднее время работы — <tex>O(1)</tex>.
==== Стоимость операции del() ======= Метод предоплаты ====Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>. При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <tex>i-\frac{n}{4}</tex>, и одну монетку на место удаленного элемента. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\frac{n}{4}</tex> удалили) у нас будет хватать денег на копирование в новый массив.==== Метод потенциалов ====За потенциал примем число <tex>\Phi=-s+\frac{1}{2}c</tex>, где <tex>s</tex> — число элементов в массиве, <tex>c</tex> — размер массива. В случае, если при удалении элемента не происходит сужение массива, стоимость операции равна: <tex>a_i=t_i+\Phi(s-1,c) - \Phi(s,c)=1+\frac{1}{2}c-s+1-\frac{1}{2}c+s=2</tex> Если же при удалении элемента происходит сужение массива, значит, число элементов после удаления стало равно <tex>\frac{1}{4}c</tex>. Тогда стоимость операции равна:
* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex>a_i=t_i+\Phi(\frac{c}{2}, s-1) - \Phi(c,s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex>* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex>a_i = t_i + \Phi(c, s- 1) - \Phi(c,cs)=1 + (\frac{1}{2}c-(s-1 ))-(\frac{1}{2}c-s)= 2</tex>* <tex dpi=150>\frac{s}{c}\ge\frac{1}{2}, \frac{s+-1+}{c}<\frac{1}{2}\cdotRightarrow s=\frac{1}{2}c </tex>, массив не сужается: <tex>a_i = t_i + \Phi(c, s-1) - \Phi(c, s) =1 +(\frac{1}{2}c -(s-1))-(2s-c)= 2+\frac{13}{42}c + 1 - 3s = 2</tex>* <tex dpi=150>\frac{s}{c}>\frac{1}{42}</tex>, массив не сужается: <tex>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1+ (2(s-1)-c)-(2s-c)=3</tex>
Средняя стоимость операции — <tex>2</tex>, а среднее время работы — <tex>O(1)</tex>.
