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>.
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>.
