python - 将元素添加到列表与在 python 中设置的时间复杂度

Question

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

Answer 1

两个操作都是 O(1) amortized时间复杂度。

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

添加x的情况下成set ，Python需要计算hash(x)首先，因为保持所有元素的散列允许集合进行快速 O(1) 成员资格检查(与列表的 O(n) 成员资格检查相比)。