这段代码的大o符号是什么？是O（n^2）还是O（n）？

Question

这里，代码检查list1是否包含list2的一些元素

result = []
    for item in list1:
        if item not in list2:
            result.append(item)

我认为复杂性将是O（n^2），因为（x in s）函数被认为是内环，对吗

Answer 1

如果set2是一个实际的set或dict它是{}，因为x in some_set将被（摊销）O(1)

如果list2是一个列表，那么它将是O(len(list1) * max_len(list2))，因为x in some_list将需要在O(len(some_list))中运行列表。所以如果两个列表都可以达到n，那么它将是O(n^2)

Answer 2

in运算符的复杂性取决于列表的类型。
如果您的列表是python的list类型，那么在here中我们可以看到（s中的x）和python中的列表具有O（n）的复杂性

因此，如果list1有n个元素，list2有m个元素，那么代码的复杂度将是O（n.m）

Answer 3

你的时间复杂度是O（n）。如果对set2变量使用hashset，“in”操作平均执行常量

如果使用两个列表，则时间复杂度为O（nm），其中n=len（列表1）和m=len（列表2）