在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
创建一个set
也具有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
a
添加了.add(..)
一些内容,则b
不会更新。 - Willem Van Onsem