Изменения

Перейти к: навигация, поиск

Динамический массив

Нет изменений в размере, 12:10, 21 января 2016
м
Стоимость операции del()
* <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>.
50
правок

Навигация