时间复杂度：删除双端队列的元素

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

E.g.:

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

Summary

时间复杂度为 O(n)，其中 n 是到最近端点的距离。总尺寸为deque不要紧。

原因

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

插图

考虑以下示例：

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

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