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

Question

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

E.g：

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

Answer 1

总结

时间复杂度为O（n），其中n是到最近端点的距离。 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”将全部向左移动一个。该算法足够智能，可以朝最接近的终点工作。

Answer 2

出队的复杂度为O（1）。由于队列始终遵循先进先出的原则，因此我们可以删除/弹出先推送的元素，而无需通过整个队列。

Answer 3

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

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

Answer 4

每docs：

索引访问在两端均为O（1），但在中间速度减慢至O（n）。要进行快速随机访问，请使用列表。