python - Python中双端队列随机访问的时间复杂度

Question

这个问题已经有答案了:

How are deques in Python implemented, and when are they worse than lists? (4 个回答)

已关闭 6 年前。

我想知道Python中deque的get操作的时间复杂度。

我知道它在Python中是作为双向链接实现的。那是不是意味着它的时间复杂度是O(n)？

Answer 1

deque 的实现比双向链表更智能一些。它们是 Python 对象 block 的双向链接列表，其中左侧和右侧可能是不完整的 block 。

中间访问的 Big-O 成本仍然是 O(n)，但它有一个常数除数(取决于实现， CPython 3.5 allocates blocks that can store 64 objects )。因此，如果您的 deque 有 1000 个成员，那么中间的访问仍然只涉及大约 7-8 次“链表式”遍历，而不是 500 次左右。如果双端队列较小(65 到 128 个元素，具体取决于空槽如何与头 block 和尾 block 对齐)，则任何元素的查找成本都是相等的。