python - Python中“set”和“if item in array”的时间复杂度是多少？

Question

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

  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