DSK*_*Kim 3 python big-o deque
我想知道Python中deque的get操作的时间复杂性.
我知道它是作为Python中的双重链接实现的.这是否意味着它的时间复杂度是O(n)？
deque实现比双链表更智能.它们是Python对象块的双向链接列表,其中左侧和右侧可能是不完整的块.
中间访问的Big-O成本仍然是O(n),但它有一个常数除数(依赖于实现,CPython 3.5分配可以存储64个对象的块).因此,如果您deque有1000个成员,那么在中间访问仍然只涉及大约7-8个"链表式"遍历,而不是500个.如果它deque是小的(65到128个元素,取决于空槽如何与头部和尾部块对齐),那么查找任何元素的成本相等.
| 归档时间： |
|
| 查看次数： |
1655 次 |
| 最近记录： |