Python 中双端队列中随机访问的时间复杂度
time complexity of random access in deque in Python
想知道Python中deque的get操作的时间复杂度。
我知道它是作为 Python 中的双重 link 实现的。这是否意味着它的时间复杂度是 O(n)？
deque 比双向链表更智能一些。它们是 Python 个对象的 块 的双向链表，其中左侧和右侧可能是不完整的块。
中间访问的 Big-O 成本仍然是 O(n)，但它有一个常数除数（取决于实现，CPython 3.5 allocates blocks that can store 64 objects）。因此，如果您的 deque 有 1000 个成员，在中间访问仍然只涉及大约 7-8 "linked list-style" 次遍历，而不是 500 次左右。如果 deque 很小（65 到 128 个元素，具体取决于空槽与头尾块的对齐方式），则查找任何元素的成本都是相等的。
想知道Python中deque的get操作的时间复杂度。
我知道它是作为 Python 中的双重 link 实现的。这是否意味着它的时间复杂度是 O(n)？
deque 比双向链表更智能一些。它们是 Python 个对象的 块 的双向链表，其中左侧和右侧可能是不完整的块。
中间访问的 Big-O 成本仍然是 O(n)，但它有一个常数除数（取决于实现，CPython 3.5 allocates blocks that can store 64 objects）。因此，如果您的 deque 有 1000 个成员，在中间访问仍然只涉及大约 7-8 "linked list-style" 次遍历，而不是 500 次左右。如果 deque 很小（65 到 128 个元素，具体取决于空槽与头尾块的对齐方式），则查找任何元素的成本都是相等的。