python 2.7 set和list消除了时间复杂性

Question

想知道移除列表和移除集合的时间复杂度。

我的思想和学习成果是

1. 删除列表是O(n)
2. 集合的删除是O(1)。

我只是研究了一些讨论，但从未证明。如果有人能关灯，那就太好了。尤其是set如何实现O(1)删除？

使用Python2.7。

a = set([1,2,3,4,5])
b = [1,2,3,4,5]

a.remove(3)
b.remove(3)

print a
print b

Answer 1

从文档中：

list.remove(x) Remove the first item from the list whose value is x. It is an error if there is no such item.

在不深入了解实现细节的情况下，要删除的项可以位于列表中的任何位置。线性扫描时间是必要的，以便在移除项目之前找到它。找到要删除的项的索引后，需要将所有元素下移一个索引。在任何情况下都会涉及到index遍历量和size - index移位量。因此，删除时间相当于遍历整个列表：O（n）。

您可以在这里找到源代码：https://hg.python.org/cpython/file/tip/Objects/listobject.c#l2197（也可以查找list_ass_slice(..)）。

---

然而，一套是不同的。它使用所存储对象的哈希值在其存储桶中定位该对象。平均而言，使用散列值定位对象的时间几乎是常数时间。注意，在散列冲突和需要进一步搜索的情况下，它可能并不总是恒定的时间。但假设一个好的散列函数，它通常是。

更新：我必须感谢Stefan Pochmann指出了错误。