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

Question

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

例如：

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

Answer 1

摘要

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

原因

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

插图

考虑以下示例：

>>> 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”将全部向左移动一个。该算法足够智能，可以朝最接近的终点工作。