我想知道Python中deque的get操作的时间复杂度。
我知道它在Python中是作为双向链接实现的。那是不是意味着它的时间复杂度是O(n)？
最佳答案
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 对齐)，则任何元素的查找成本都是相等的。
关于python - Python中双端队列随机访问的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39522787/