Python中两个列表公共元素检测函数的时间复杂度分析与性能对比

首先得澄清你最困惑的点：Python中in运算符的时间复杂度取决于它作用的数据结构——这也是两个函数性能差异的核心原因。

一、func1的时间复杂度 #

先看你的func1代码：

def func1(list1, list2):
    for i in list1: # O(n)，n是list1的长度
        if i in list2: # 这里的时间复杂度是关键
            return True
    return False

Python的列表是线性结构，element in list本质上是顺序遍历查找：从列表第一个元素开始逐个比对，直到找到目标元素或者遍历完整个列表。所以这个操作的时间复杂度是O(m)，其中m是list2的长度。

那func1的最坏情况是什么？就是两个列表完全没有公共元素，这时候我们要遍历list1的所有n个元素，每个元素都要完整遍历list2的m个元素才能确定不存在。因此func1的最坏时间复杂度是O(n*m)（二次时间复杂度）。

当然最好情况是list1的第一个元素就出现在list2里，这时候时间复杂度是O(1)（只需要一次查找），但我们分析算法复杂度通常关注最坏情况。

二、func2的时间复杂度 #

再看func2的实现：

def func2(list1, list2):
    dict = {}
    for i in list1:
        if i not in dict.keys():
            dict[i] = True
    for j in list2:
        if j in dict.keys():
            return True
    return False

这里用到了字典（哈希表），而字典的键查找是Python中效率很高的操作：

1. 第一步：遍历list1构建字典。for i in list1是O(n)，而i not in dict.keys()（其实直接写i not in dict效果完全一样）的时间复杂度是平均O(1)——因为字典通过哈希表直接定位键的位置，不需要遍历。所以这一步的总时间是O(n)。
2. 第二步：遍历list2检查元素是否在字典中。for j in list2是O(m)，每个j in dict.keys()同样是平均O(1)，所以这一步总时间是O(m)。

把两步加起来，func2的最坏时间复杂度是O(n + m)（线性时间复杂度），比func1的二次复杂度高效得多。

三、两个函数的性能差异 #

1. 时间效率差异：当列表规模较小时，两者的性能差距可能不明显，但当n和m都很大时（比如都是1000个元素），func1最坏要执行100万次操作，而func2只需要2000次左右，差距会非常显著。
2. 空间复杂度 trade-off：func1不需要额外的存储空间，空间复杂度是O(1)；而func2需要用字典存储list1的所有元素，空间复杂度是O(n)——这是典型的「用空间换时间」的策略。
3. 极端情况说明：字典的键查找虽然平均是O(1)，但极端情况下（比如所有键的哈希值都冲突）会退化到O(n)，不过这种情况在实际开发中几乎不会遇到，所以可以放心认为是O(1)的平均性能。

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