在 Python 中“冻结”一个集合的计算复杂度是多少?
例如,第二行在
a = {1,2,3}
b = frozenset(a)
需要 O(n) 时间?或者它只是在恒定时间内创建的“视图”?
在 Python 中“冻结”一个集合的计算复杂度是多少?
例如,第二行在
a = {1,2,3}
b = frozenset(a)
需要 O(n) 时间?或者它只是在恒定时间内创建的“视图”?
b
不是一个观点a
。您可以通过以下方式检查id
:
a = {1, 2, 3}
b = a
id(a) == id(b) # True
b = frozenset({1, 2, 3})
id(a) == id(b) # False
因此,变化b
不会反映在 中a
。当然,您可以自己测试一下。由于frozenset
将可迭代对象作为参数,因此它必须遍历每个参数。这是一个 O( n ) 过程。
顺便说一句,没有什么特别的frozenset
,即使set
从 a创建 aset
也有 O( n ) 时间复杂度:
for i in [10**5, 10**6, 10**7]:
a = set(range(i))
%timeit set(a)
100 loops, best of 3: 3.33 ms per loop
10 loops, best of 3: 30.2 ms per loop
1 loop, best of 3: 421 ms per loop