python 2.7 设置和列表删除时间复杂度 [英] python 2.7 set and list remove time complexity

问题描述

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

Wondering the time complexity of remove of list, and remove of set.

我的想法和研究结果是，

My thought and study result is,

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

我只是研究了一些讨论，但从未证明过.如果有人能点亮一些灯，那就太好了.尤其是 set 是如何通过 O(1) 移除实现的?

I just studied some discussion, but never prove it. If anyone could shed some lights, it will be great. Especially how set implements with O(1) removal?

使用 Python 2.7.

Using 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

推荐答案

来自文档:

list.remove(x)从列表中删除值为 x 的第一项.如果没有这个项目是错误的.

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).

Without going into the details of the implementation, the item to remove can be anywhere in the list. A linear scan time is necessary in order to find the item before it can be removed. Once you find the index of the item to remove, you need to shift all the elements down by one index. In any case there's index amount of traversal and size - index amount of shifting involved. Therefore the removal time is equivalent to traversing the entire list: O(n).

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

You can find the source here: https://hg.python.org/cpython/file/tip/Objects/listobject.c#l2197 (also look for list_ass_slice(..)).

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

However, a set is different. It uses the hash value of the object being stored to locate it in its buckets. On an average, locating of objects using hash value is almost constant time. Note that it might not always be constant time where there's hash collision and a further search is required. But assuming a good hash function, it usually is.

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

UPDATE: I must thank Stefan Pochmann for pointing out the mistake.

这篇关于python 2.7 设置和列表删除时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！