时间戳

首页 > 解决方案 > 在 Python 中将集合转换为冻结集的复杂性

python - 在 Python 中将集合转换为冻结集的复杂性

问题描述

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

例如，第二行在

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

需要 O(n) 时间？或者它只是在恒定时间内创建的“视图”？

标签： pythonsettime-complexityfrozenset

解决方案

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

推荐阅读