python 2.7 set和list删除时间复杂度

Question

想知道删除列表的时间复杂度,并删除集合.

我的思想和研究结果是,

1. 删除列表是 O(n)
2. 去除集是O(1).

我刚学了一些讨论,但从未证明过.如果有人可以摆脱一些灯光,它会很棒.特别是如何设置O(1)删除？

使用Python 2.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)从列表中 删除值为x 的第一个项目.如果没有这样的项目则是错误的.

在不进入实现细节的情况下,要删除的项目可以在列表中的任何位置.线性扫描时间是必要的,以便在可以移除之前找到该项目.找到要删除的项目的索引后,需要将所有元素向下移动一个索引.在任何情况下都存在index 大量的遍历和size - index转移量.因此,删除时间相当于遍历整个列表:O(n).

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

但是,一组是不同的.它使用存储对象的哈希值在其存储桶中定位它.平均而言,使用散列值定位对象几乎是恒定的时间.请注意,它可能并不总是恒定的时间,其中存在哈希冲突并且需要进一步搜索.但是假设一个好的哈希函数,它通常是.

更新:我必须感谢Stefan Pochmann指出了这个错误.