gpt4 book ai didi

python - 在 Python 中将集合转换为卡住集的复杂性

转载 作者:太空宇宙 更新时间:2023-11-04 02:16:15 24 4
gpt4 key购买 nike

在 Python 中“卡住”一个集合的计算复杂度是多少?

例如,第二行是

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

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

最佳答案

b 不是 a 的 View 。您可以通过 id 查看:

a = {1, 2, 3}
b = a

id(a) == id(b) # True

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

id(a) == id(b) # False

因此,b 中的更改不会反射(reflect)在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

关于python - 在 Python 中将集合转换为卡住集的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52590502/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com