在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

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

Answer 4

由于它是用

hashtable

实现的，理论上最坏情况的复杂度为 O(n^2)。根据列表中的项目，散列操作可能会尝试将它们全部分配到相同的内存插槽，在这种情况下，它会迭代冲突链以查找可用空间。虽然我不确定实现这种情况需要什么样的项目列表。