list（…）.insert（…）的性能

list（…）.insert（…）的性能

Python是一种语言。存在多种实现，并且它们可能具有列表的不同实现。因此，如果不查看实际实现的代码，就无法确定列表的实现方式以及它们在某些情况下的行为。

我敢打赌，列表中对象的引用存储在连续内存中（肯定不是链接列表…）。如果确实如此，则使用插入x.insert将导致移动所插入元素后面的所有元素。这可以通过硬件有效地完成，但是复杂度仍然是O（n）。

对于小列表，该bisect *** 作可能需要花费更多时间

x.insert

，即使前者是

O（log n）

而后者是

O（n）

。但是，对于长列表，我可能会猜测

x.insert

是瓶颈。在这种情况下，您必须考虑使用其他数据结构。