Python中将集合转换为列表的算法复杂度

Question

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

我希望了解复杂度是否像Python中许多其他事情一样是常量。

- macetw

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)

这张图清晰地展示了线性关系——除了一些噪声。

(因为第一个版本的基准测试内容不同，所以进行了编辑。)

- norok2

---

那么在1000和6000发生了什么？我知道整体形状表示O(N)，我只是好奇这些步骤显示了哪些实现细节。 - Andrew Jaffe

我认为跳跃的原因是列表实现在增长时分配了额外的空间，但当它达到极限时必须重新分配列表。 - Barmar

这不是衡量操作时间复杂度的方法；时间复杂度是理论上的，只适用于“足够大”的n，其中20000可能并不“足够大”。这个图表提供了一些关于时间复杂度可能是什么的证据，但你不能通过实际运行算法并使用计时器来测量算法的时间复杂度。 - kaya3

@kaya3 当然。我仍然发现这种启发式方法有助于理解我们应该在实际应用中期望什么样的行为。此外，这个问题相当实际。有多种方法来定义像set()和list()这样的容器，这些方法在未来的实现中可能会有所不同，而这个简单的启发式方法将在不知道内部情况的情况下提供洞察力。 - norok2

@AndrewJaffe 这是集合的内部大小，在这些点上会增加四倍。 - Kelly Bundy

@AndrewJaffe 请看时间 vs 设置大小的图表。 - Kelly Bundy

Answer 2

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

• 该集合被实现为哈希表，其底层数组的大小受到集合大小的固定倍数的限制。遍历集合是通过遍历底层数组完成的，所以需要O（n ）的时间。
• 即使列表的底层数组最初未分配足够整个集合所需的空间，将项目附加到列表需要摊销O（1）的时间；因此将n 个项目附加到空列表需要O（n ）的时间。

但是，这里有一个重要说明，即Python的集合具有基于集合对象曾经拥有的最大大小的底层数组大小，而不一定基于其当前大小；这是因为当从集合中删除元素时，底层数组不会重新分配为较小的大小。如果集合很小但曾经很大，则对其进行迭代可能比O（n ）慢。

- kaya3

Answer 3

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

- Serge Ballesta