Python - это язык. Существует несколько реализаций , и они могут иметь разные реализации для списков. Таким образом, не глядя на код реальной реализации, вы не можете точно знать, как реализованы списки и как они ведут себя при определенных обстоятельствах.
Могу поспорить, что ссылки на объекты в списке хранятся в непрерывной памяти (конечно, не в виде связанного списка ...). Если это действительно так, то вставка с использованием x.insert
приведет к перемещению всех элементов за вставленным элементом. Это может быть эффективно сделано аппаратными средствами, но сложность все равно будет O (n) .
Для небольших списков операция bisect
может занять больше времени, чем x.insert
, даже если первый O (log n) , а последний O (n), Однако для длинных списков я бы рискнул предположить, что узким местом является x.insert
. В таких случаях вы должны рассмотреть возможность использования другой структуры данных.