以下代码的 python 中“in”的时间复杂度

Question

arr1 = ["a","b","c","d"]
arr2 = ["x","y","z","c"]

obj = dict()

for i in range(len(arr1)):
    if arr1[i] in obj:
        continue
    else:
        obj[arr1[i]] = "true"

print(obj)

for j in range(len(arr2)):
    if (arr2[j] in obj):
        print("true")
    else:
        print("false")

我正在尝试遍历数组（arr2）并检查数组项是否在字典（obj）中（在第一个 for 循环中创建）。这里我使用“in”来检查它是否在字典（obj）中。 “in”的时间复杂度是多少？是 O(n)，如果是，那么将有 2 个嵌套的 for 循环，这将使它成为 O(n^2)。

我希望上述问题的时间复杂度为 O(n)。如果此解决方案给出 O(n^2) 时间复杂度，还有其他方法吗？

Answer 1

复杂度平均为 O(1)，最坏情况为 O(n)

参考