Python 中 "set" 和 "if item in array" 的时间复杂度是多少？
What is Time complexity of "set" and "if item in array" in Python?
我需要检查数组中是否存在数字及其双精度值。此代码使用 set 来解决它。但是我不确定时间复杂度是否优于 O(N^2)。我使用 for loop 和 if 2*item in s 如下所示。不就是知道item是否在一个数组中吗，我们又用了一个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
对于 python 中的集合，'in' 运算符的时间复杂度平均为 O(1)，仅在最坏情况下为 O(N)，因为集合在 python 中在内部使用哈希表。
所以你的函数的平均时间复杂度应该是 O(N)，只有在最坏的情况下才会是 O(N^2)，其中 N 是数组的长度。
我需要检查数组中是否存在数字及其双精度值。此代码使用 set 来解决它。但是我不确定时间复杂度是否优于 O(N^2)。我使用 for loop 和 if 2*item in s 如下所示。不就是知道item是否在一个数组中吗，我们又用了一个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
对于 python 中的集合，'in' 运算符的时间复杂度平均为 O(1)，仅在最坏情况下为 O(N)，因为集合在 python 中在内部使用哈希表。
所以你的函数的平均时间复杂度应该是 O(N)，只有在最坏的情况下才会是 O(N^2)，其中 N 是数组的长度。