python - 时间复杂度 : deleting element of deque

Question

删除 collections.deque 的一个元素的时间复杂度是多少？

例如:

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

Answer 1

总结

时间复杂度为 O(n)，其中 n 是到最近端点的距离。 双端队列 的总大小无关紧要。

原因

deque 的实现是一个固定长度 block 的双向链表。删除一个元素需要在删除点和最近的端点之间单独移动所有元素。

插图

考虑以下示例:

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

为了便于说明，假设以下数据布局的 block 大小为 3(实际 block 大小为 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”将全部向左移动一位。该算法足够智能，可以朝着最近的终点努力。