Python中雙向隨機訪問的時間複雜度

Question

我很想知道在Python中獲取deque操作的時間複雜度。

我知道它是作爲Python中的雙向鏈接實現的。這是否意味着它的時間複雜度是O（n）？

Answer 1

deque實現比雙向鏈表更聰明一點。它們是Python對象的雙向鏈接列表塊，其中左側和右側可能是不完整的塊。

在中間訪問的大O成本仍然是O(n)，但它有一個不變除數（取決於實現，CPython 3.5 allocates blocks that can store 64 objects）。因此，如果您的deque有1000個成員，則在中間訪問仍然只涉及大約7-8個「鏈接列表式」遍歷，而不是500個。如果deque很小（65到128個元素，取決於空槽如何與頭部和尾部塊對齊），那麼查找任何元素都是等價的。