Сложность времени: удаление элемента deque

Question

Какова временная сложность удаления элемента collections.deque?

Например:

deq = collections.deque([1, 2, 3])
del deq[1]

Answer 1

Сводка

Сложность по времени составляет O (n), где n - расстояние до ближайшей конечной точки.Общий размер deque не имеет значения.

Причина, по которой

Реализация deque представляет собой двусвязный списокблоки фиксированной длины.Удаление элемента требует индивидуального перемещения всех элементов между удаленной точкой и ближайшей конечной точкой.

Иллюстрация

Рассмотрим следующий пример:

>>> d = deque('abcdefghijklmnop')
>>> del d[3]

В целях иллюстрациипредположим, что размер блока равен трем (фактический размер блока равен 64) для следующего макета данных:

ab  ⇄  cde  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     # State before deletion
        ×                                     # Step 1, delete "d"
ab  ⇄  c-e  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     
       →                                      # Step 2, move "c" to right 
ab  ⇄  -ce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op  
 →                                            # Step 3, move "b" to right
a-  ⇄  bce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op  
→                                             # Step 4, move "a" to right
 a  ⇄  bce  ⇄  fgh  ⇄  ijk  ⇄  lmn  ⇄  op     # Final state after deletion     

Как видите, элементы данных между удаленным элементом и конечной точкой должныпереместитесь на единицу вправо.

Если бы "k" было удалено, все элементы "lmnop" сместились бы один влево.Алгоритм достаточно умен, чтобы работать в направлении ближайшей конечной точки.