Skip to main content
 首页 » 编程设计

python之python中的list(set)操作是O(1)吗

2025年01月19日9hnrainll

如果我们想从一个集合构造一个列表,我们可以这样做

[k for k in set] 

这是 O(n) 操作,同时:

dict.keys() 

是 O(1) 根据 https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

因此,据我所知,dict是使用set作为底层数据结构的key,是list(set) O(1)吗?这是如何实现的?

a = set(range(n)) 
s = list(a) # is this operation O(1)? 

请您参考如下方法:

Thus, as far as I know, dict is using set as its keys underlying data structure.

嗯,不,不是真的。相反的方法是一个更接近的类比:在实现中,set 就像一个包含所有空值的 dict。 dict 首先出现在 Python 中,set 直到 Python 2.2(2000 年 7 月)才出现 - 参见 PEP 218 .

另外值得一提的是 dict.keys() 自 Python 3 以来是 O(1)。在 Python 2 中它是 O(n),你应该使用 dict.viewkeys() 用于键“ View ”(类似设置的界面)。

is list(set) O(1)?

不,它是 O(n) - 与列表理解相同。

And how is this implemented?

设置支持the iterator protocol .