大 O 表示法 |时间复杂度 - 带有 'and' 关键字的嵌套循环

Question

我正在 Python 学习大 O 表示法。

我不清楚以下代码的时间复杂度是多少：

for elem in list_1:
    if elem in list_2 and elem in list_3:
        print(elem)

你怎么看？

Answer 1

如果list1、list2、list3的大小分别用m、n、p表示，时间复杂度为 O(m * (n + p))。因为外层循环运行了m次，而在每次迭代中条件if可以进行O(n + p)比较来检查elem是否包含在相应的列表中。