Python中双端队列中随机访问的时间复杂度 [英] time complexity of random access in deque in Python

问题描述

我想知道Python中双端队列的get操作的时间复杂度.

I am wondering about the time complexity of the get operation of deque in Python.

我知道它在Python中被实现为双向链接.这是否意味着其时间复杂度为O(n)?

I know that it is implemented as a doubly link in Python. Does that mean that its time complexity is O(n)?

推荐答案

deque的实现比双链列表要聪明得多.它们是Python对象的 blocks 的双向链接列表，其中左侧和右侧可能是不完整的blocks.

deque are implemented a little smarter than just doubly-linked lists. They're a doubly-linked list of blocks of Python objects, where the left and right sides may be incomplete blocks.

在中间访问的Big-O成本仍然是O(n)，但是它具有恒定的除数(取决于实现，deque很小(65到128个元素，具体取决于空插槽与头部和尾部对齐的方式)，则任何元素的查找成本均相等.

The Big-O cost of accessing in the middle is still O(n), but it has a constant divisor (implementation dependent, CPython 3.5 allocates blocks that can store 64 objects). So if your deque has 1000 members, accessing in the middle still involves only around 7-8 "linked list-style" traversals, not 500-some. If the deque is smallish (65 to 128 elements, depending on how the empty slots align with the head and tail blocks), then lookup of any element is equal cost.

这篇关于Python中双端队列中随机访问的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！