Какова алгоритмическая сложность конвертирования collection.deque в список python?

Question

Я пытаюсь определить сложность преобразования объекта collection.deque в объект списка Python O (n).Я полагаю, что потребуется взять каждый элемент и преобразовать его в список, но я не могу найти код реализации позади deque.Итак, встроил ли Python что-то более эффективное изнутри, что могло бы обеспечить преобразование O (1) в список?

Редактировать: Исходя из следующего, я не верю, что это может быть быстрее, чем O (n)«Индексированный доступ - это O (1) на обоих концах, но в середине он замедляется до O (n). Для быстрого произвольного доступа вместо этого используйте списки.»

Если он не может получить доступ к среднему узлу в O (1)Время не сможет конвертировать без такой же сложности.

Answer 1

Вот реализация deque

Однако это не имеет значения для определения сложности преобразования deque в список в python.

Если python каким-то образом не использует структуру данных для внутреннего использования, преобразование в список потребует обхода deque, и это будет O (n).

Answer 2

Вы должны получить доступ к каждому узлу.O (1) время невозможно только для этого факта.

Я бы полагал, что deque следует тем же принципам, что и обычные deques , в том смысле, что для доступа к первому элементу требуется постоянное время.Вы должны сделать это для n элементов, поэтому время выполнения для этого будет O (n).