Python中：遍历短列表搜长列表VS遍历长列表搜短列表，哪种更高效？

在不使用集合的前提下，方案(a)的效率明显高于方案(b)，原因如下：

时间开销拆解 #

Python中列表的in操作是线性扫描，时间复杂度为O(k)（k为列表长度）。我们可以把两种方案的总开销拆成两部分：循环迭代的固定开销，以及元素查找的比较开销：

假设：

• large_list长度为N（比如10000）

• small_list长度为M（比如100）

• 单次循环迭代的固定开销为D

• 单次元素比较的开销为C

• 方案(a)：循环M次（100次），每次在长度为N的列表中查找。总开销为：M*D + M*(N/2)*C（平均每次扫描到列表中间找到元素，所以乘以N/2）

• 方案(b)：循环N次（10000次），每次在长度为M的列表中查找。总开销为：N*D + N*(M/2)*C

两者的元素比较总开销是相等的（都是(M*N*C)/2），但循环迭代的固定开销差异极大：方案(a)只需要100次循环，而方案(b)需要10000次，这部分开销会让方案(b)的整体运行时间远高于方案(a)。

最优方案补充 #

你提到的集合方案确实是最优解：将large_list转为集合large_set = set(large_list)（时间复杂度O(N)），再遍历small_list进行查找（每次in操作O(1)，总O(M)），整体时间复杂度O(N+M)，比(a)(b)的O(N*M)效率提升几个数量级。

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