时间复杂度：删除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]

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