python - 在python中将集合转换为列表的算法复杂度

Question

在 python 中，当我将我的集合转换为列表时，这样的任务的算法复杂度是多少？它只是对集合进行类型转换，还是需要将项目复制到不同的数据结构中？发生了什么？

我很想知道复杂性是恒定的，就像 Python 中的很多东西一样。

Answer 1

您可以通过简单的基准测试轻松看到这一点：

import matplotlib.pyplot as plt


x = list(range(10, 20000, 20))
y = []
for n in x:
    s = set(range(n))
    res = %timeit -r2 -n2 -q -o list(s)
    y.append(res.best)


plt.plot(x, y)

这清楚地显示了一种线性关系——以一些噪声为模。

（编辑为第一个版本是对不同的东西进行基准测试）。

Answer 2

大多数情况下的时间复杂度为 O( n )，其中n是集合的大小，因为：

• 该集合被实现为一个哈希表，其底层数组大小由集合大小的固定倍数限制。对集合的迭代是通过对底层数组进行迭代来完成的，因此需要 O( n ) 时间。
• 将一个项目附加到列表需要 O(1) 分摊时间，即使列表的底层数组最初没有分配到足够大以容纳整个集合；因此将n 个项目附加到一个空列表需要 O( n ) 时间。

但是，有一个警告，即 Python 的集合具有基于集合对象具有的最大大小的底层数组大小，不一定基于其当前大小；这是因为从集合中删除元素时，底层数组不会重新分配到较小的大小。如果一个集合很小但曾经大得多，那么迭代它可能比 O( n ) 慢。

Answer 3

复杂性是线性的，因为所有引用都被复制到新容器中。但只有引用和是而不是对象 - 它对于大对象可能很重要。