3622
правки
Изменения
Нет описания правки
Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> O(\log ~n) </tex>
== Описание асипмтотики ==
Рассмотрим поподробнее асимптотику операций. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Этот элемент встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Добавим третий элемент. После предыдущего действия появилась свободная вакансия на место левого ребёнка дека первого уровня, поэтому новый элемент занимает это место. И, наконец, добавим 4-ый элемент. Он объединяется в пару с левым ребёнком дека первого уровня, затем новая пара объединяется со старой парой на втором уровне и добавляется в дек на высоте 2. И так далее.
[[Файл:PushDequeExample.png]]
Таким образом, если мы добавляем элементы только в один конец, то на <tex> i </tex>-ом уровне дека не более <tex> 2^i </tex> элементов. Пусть высота текущего дека <tex> h. </tex> Тогда в нём может находится не более <tex> n ~=~ 1 ~+~ 2 ~+~ 4 ~+...+~ 2^h </tex> объектов, откуда получаем <tex> h = \mathcal{b} \log_2 ~n \mathcal{c} </tex>.
== См. также ==
