Python中set()的运行时间

Question

我在想，查找一个集合（set()）的时间复杂度是 O(1) 还是 O(n) 呢？

如果我有：

x = set()

那么下面这段代码的运行时间是多少呢：

如果 "a" 在 x 里面：

打印 "a 在集合里！"

Answer 1

set 是通过一种叫做哈希的方式来实现的，这样查找的速度通常是接近 O(1) 的。也就是说，查找的时间几乎是固定的，不会随着数据量的增加而变慢。不过在最糟糕的情况下，如果有 n 个对象的哈希值发生了冲突，那么查找的时间就会变成 O(n)，也就是查找的时间会随着对象数量的增加而增加。