具有lambda函数的filter()的复杂性分析

Question

给出两个列表,list1和list2

list3 = filter(lambda x: x in list1,list2)

这将返回两个列表的交集.

如何找到此算法的复杂性？我发现时间复杂度x in list1是O(n),其中n是列表中元素的数量,但是如何filter？

Answer 1

您的代码执行O(len(list1) * len(list2))元素的比较操作.

• 您的lambda函数执行O(len(list2))次数,每个元素被过滤一次.请参阅filterPython 3(Python 2)中的文档:

  filter(function, iterable)

  iterator从函数返回true的那些元素iterable构造一个.iterable可以是序列,支持迭代的容器,也可以是迭代器

  (强调我的)

  显然,对于iterable中的每个(不同)元素,函数被调用至少一次 - 知道什么时候不需要调用它也意味着在一般情况下也解决Halting问题,甚至Python核心开发人员还没有解决;-) .在CPython的3实践中filter内置创建一个迭代其中当推进,在迭代顺序的每个元素(不同或不)执行一次函数.

• 如记录所述x in list1,O(len(list1))在平均和最差情况下进行比较.

为了加快速度,请使用set; 你根本不需要lambda函数(使用__contains__魔法)

list3 = filter(set(list1).__contains__, list2)

这将构建一个set的list1曾经在O(len(list1))时间和运行过滤反对与O(len(list2))平均水平的复杂性O(len(list1) + len(list2))

如果元素的排序list2 无关紧要,那么你也可以这样做

set(list1).intersection(list2)

应该具有比filter上述更低的常数; 对于真正快速的代码,您应该对列表进行排序,以便将较小的代码转换为集合(因为交集和集合构建都记录了平均复杂度O(n),但是由于调整大小set,集合构建最可能会有更大的常量,因此它将有意义的是从较小的构建集合以减少这些常量的权重):

smaller, larger = sorted([list1, list2], key=len)
result = set(smaller).intersection(larger)

请注意,Python 2和3彼此不同.filter在Python 3中返回一个生成器,实际运行时间取决于生成的生成器消耗的元素数量,而在Python 2中,将预先生成一个列表,如果只需要第一个值,这可能会更昂贵.