为何混合列表/集合推导式求列表交集的时间复杂度为O(n)优于纯列表推导式？

我有两个计算整数数组交集的函数，第二种结合集合的混合列表推导式时间复杂度为O(n)，但纯列表推导式的时间复杂度高于O(n)。作为刚接触大O符号的新手，我搞不懂其中的原因，希望有人能解释清楚。

纯列表推导式实现： #

def intersection(lst1, lst2):
    lst3 = [value for value in lst1 if value in lst2]
    return lst3

结合集合的混合列表推导式实现： #

def intersection(lst1, lst2):
    temp = set(lst2)
    lst3 = [value for value in lst1 if value in temp]
    return lst3

核心原因：列表和集合的查找效率天差地别 #

要搞懂时间复杂度的差异，关键看value in X这个操作的开销：

• 列表的查找是线性遍历：每次判断value in lst2，程序会从lst2的第一个元素开始逐个比对，直到找到目标或者遍历完整个列表。这个操作的时间复杂度是O(m)，其中m是lst2的长度。
• 集合的查找是哈希表查询：集合底层用哈希表实现，查找元素时直接通过哈希值定位，平均情况下不管集合多大，单次查找的时间都是O(1)（固定时间）。

两种实现的时间复杂度拆解 #

1. 纯列表推导式：
   假设lst1长度为n，lst2长度为m。我们要遍历lst1的n个元素，每个元素都要做一次O(m)的列表查找，总时间复杂度是O(n*m)。这是二次时间复杂度，远高于线性的O(n)，当n和m都比较大时，性能会急剧下降。

2. 结合集合的实现：

   • 第一步把lst2转成集合：遍历lst2的m个元素，每个元素插入集合的操作是O(1)，这部分时间复杂度是O(m)。
   • 第二步遍历lst1查找：遍历lst1的n个元素，每个元素做一次O(1)的集合查找，这部分时间复杂度是O(n)。
     总时间复杂度是O(m + n)，当n和m属于同一量级时，大O符号会忽略次要项，简化为O(n)，也就是线性时间复杂度，比纯列表实现高效得多。

举个直观的例子：如果lst1和lst2各有1000个元素，纯列表版本要执行1000*1000=100万次比对操作，而集合版本只需要1000（转集合）+1000（查找）=2000次操作，差距一眼就能看出来。

内容的提问来源于stack exchange，提问作者SCQs