在某个位置插入列表的成本/复杂性是多少? [英] What is the cost/ complexity of insert in list at some location?

问题描述

在Python中，列表具有将项目插入到给定位置.".在C ++中，也有一个列表.在C ++中，在任何位置插入元素的成本/复杂度为O(1). Python列表是否相同?如果不是，是否可以使用其他方法在Python中获得O(1)插入时间?

In Python, a list has list.insert(i, x) to "Insert an item at a given position.". In C++, there is a list as well. In C++, cost/complexity of inserting an element anywhere is O(1). Is it the same for a Python list? If not, can anything else be use to get O(1) insert time in Python?

推荐答案

Python语言未指定此类操作的实现，因此不同的实现可能具有不同的行为.对于CPython，list.insert的复杂度为O(n)，如此有用的Wiki页面所示.我不知道有任何类似列表的结构可为在任意索引处插入提供O(1)性能. (一个dict在一般情况下可提供O(1)插入性能，但没有排序，并且不强制执行连续的索引序列.)

The Python language doesn't specify the implementation of such operations, so different implementations may have different behavior. For CPython, the complexity of list.insert is O(n), as shown on this useful wiki page. I'm not aware of any list-like structure giving O(1) performance for inserting at an arbitrary index. (A dict gives O(1) insert performance in the average case, but is not ordered and does not enforce a contiguous sequence of indices.) The blist library provides an optimized list type that has an O(log n) insert.

这篇关于在某个位置插入列表的成本/复杂性是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！