Python中向列表和集合添加元素的时间复杂度。

Question

为什么在Python中向集合添加元素比向列表添加元素需要更长的时间？我创建了一个循环，迭代了1000000个元素并将其添加到列表和集合中。列表通常需要大约10秒钟，而集合需要大约20秒钟。

- Punter Vicky

Answer 1

这两个操作的时间复杂度都是O(1) 平摊的。

将元素添加到列表中的系数较低，因为它不需要先对元素进行哈希，也不需要检查/处理哈希冲突。

在将x加入到set中时，Python 需要首先计算hash(x)，因为保持所有元素的哈希值是集合能够快速实现O(1)成员检查（相比于列表的O(n)成员检查）的原因。

- wim

---

是的。绝对来说它会慢一些，但它不会因为集合/列表的大小而变得更慢。 - wim

在执行插入操作之前，是否需要进行o(log n)的检查以查看项目是否已经存在于集合中？ - Punter Vicky

不是的。这是O(1)摊销。 - wim

不，哈希表的成员测试是O(1)，而不是O(log n) - 而且成员测试是在探测要插入的索引时完成的。 - kaya3

哈希表会告诉你在内存中填充一个元素的位置，如果那个位置已经被一个不相等的对象占据了，那么您就有一个确定性的“扰动”算法来告诉您如何找到其他索引来使用。存储空间会动态调整大小，以便通常只需要探测0或1次，无论集合的大小如何。这就是您能够获得平均* O（1）*的方式，但是当需要重新分配存储时，它有时会明显变慢（顺便说一下，对于集合和列表都是如此）。 - wim

Answer 2

向列表添加元素的时间复杂度与向集合添加元素的时间复杂度相同，都是O(1)的摊销操作，这意味着它们平均每个操作需要固定的时间量，尽管偶尔可能需要更多的时间来动态调整存储数据的数组的大小。

然而，仅仅因为它们都是O(1)并不意味着它们需要相同的时间：

- 向列表添加元素应该更快，因为列表被实现为动态数组，所以添加一个元素只需要将该元素写入正确的索引（已知），并增加长度1。 - 相反，添加到集合中则较慢，因为它需要计算元素的哈希值以找到开始查找的索引，然后按某个序列测试索引以查看该元素是否已经存在（通过测试索引处是否有元素，如果有，则测试它是否等于要插入的元素），直到找到它或找到应添加元素的空间。

- kaya3

---

“然后测试从该索引开始的每个元素” <-- 这是不正确的，Python不使用线性探测。 - wim

@wim 你说得对，我记错了这个细节，所以感谢你的纠正。维基百科似乎没有关于Python使用的特定方案的文章，因此我已将链接替换为通用链接。 - kaya3