問題

刪除collections.deque元素的時間複雜性是什麼?

例如:

 deq = collections.deque([1, 2, 3])
del deq[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     
 

正如您所看到的,刪除元素和 end-point 之間的資料元素都必須一個向右移動。

如果刪除“k”,元素“lmnop”都會移動左邊的一個,這個演算法足夠聰明,能夠達到最接近的最終點。

  相同標籤的其他問題

pythonalgorithmdata-structurestime-complexitydeque