Мне интересно о временной сложности операции get deque в Python.временная сложность случайного доступа в deque в Python
Я знаю, что он реализован как двойная ссылка в Python. Означает ли это, что его временной сложностью является O (n)?
deque реализованы немного умнее, чем только дважды связанные списки. Они представляют собой двусвязный список из блоков объектов Python, где левая и правая стороны могут быть незавершенными.
Стоимость доступа к середину по-прежнему равна O(n), но имеет постоянный делитель (зависит от реализации, CPython 3.5 allocates blocks that can store 64 objects). Поэтому, если ваш deque имеет 1000 членов, доступ посередине по-прежнему включает в себя только около 7-8 «связанных списков», а не 500-некоторые. Если deque является небольшим (от 65 до 128 элементов, в зависимости от того, как пустые слоты выравниваются с головным и хвостовым блоками), то поиск любого элемента равен стоимости.
Также обратите внимание на документацию [«Индексированный доступ - это O (1) с обоих концов, но замедляется до O (n) в середине».] (Https://docs.python.org/3/library/collections.html# collections.deque.maxlen) – metatoaster