在Python中将一个集合转换为不可变集合的复杂性

Question

在Python中“冻结”一个集合的计算复杂度是什么？

例如，第二行代码：

a = {1,2,3}
b = frozenset(a)

需要O(n)的时间吗？还是仅仅是在常数时间内创建了一个“视图”？

- erensezener

---

这不是一个视图，因为如果您稍后向 a 添加了 .add(..) 一些内容，则 b 不会更新。 - Willem Van Onsem

构造函数的时间复杂度与参数可迭代元素数量成线性关系。 - Willem Van Onsem

因此，构建的时间复杂度为O(n)。插入单个元素的最坏情况时间复杂度可能达到O(n)，但是平摊成本为*O(1)*。 - Willem Van Onsem

为什么不直接创建一个大集合并尝试呢？从单个测试中应该非常明显。 - John Zwinck

Answer 1

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   

- jpp