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个元素，取决于空槽如何与头部和尾部块对齐），那么查找任何元素都是等价的。