Python 中"set"和"if item in array"的时间复杂度是多少？

Question

我需要检查数组中是否存在数字及其双精度。这个代码使用set来解决它。但是我不确定时间复杂度是否比O(N^2)更好。我使用for loop和if 2*item in s，如下所示。不是要知道该项是否在数组中吗？我们使用另一个O(N)。O(N^2)总共是什么意思？如果它是最优的，我如何在不使用nested loop的情况下实现C中的代码
非常感谢！

def checkIfExist(arr]) -> bool:
s = set(array)
for item in s:
if 2 * item in s and item != 0:
return True
if arr.count(0) >= 2:
return True
return False

Answer 1

python中集合的'in'运算符的时间复杂度平均为O(1(，仅在最坏的情况下为O(N(，因为python中的集合在内部使用HashTable。

因此，函数的时间复杂度平均应该是O(N(，只有在最坏的情况下才会是O(N^2(，其中N是数组的长度。

点击此处了解更多信息https://wiki.python.org/moin/TimeComplexity