在某个位置插入列表的成本复杂性是多少？

在某个位置插入列表的成本/复杂性是多少？

Python语言未指定此类 *** 作的实现，因此不同的实现可能具有不同的行为。对于CPython，

list.insert

如该有用的Wiki页面所示，其复杂度为O（n）。我不知道任何提供O（1）性能的类似列表的结构，可以在任意索引处插入。（字典在一般情况下可提供O（1）插入性能，但没有排序，并且不强制执行连续的索引序列。）该

blist

库提供了具有O（log
n）插入的优化列表类型。