355
правок
Изменения
м
→Метод потенциалов
При каждой операции будем использовать три монетки. Одну из них потратим на само удаление элемента, одну монету на элемент, стоящий на позиции <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,\frac{1}{2}c) - \Phi(s,c)=s-1 -s+1+\frac{1}{2}\cdot\frac{1}{2}c + s-\frac{1}{2}c = \frac{1}{4}c + 1 - \frac{1}{4}c=1</tex>
Средняя стоимость операции - — <tex>2</tex>, а среднее время работы - — <tex>O(1)</tex>.
