Python中字典'in'操作时间复杂度及O(n)实现方案咨询

一、字典in操作的时间复杂度 #

Python的字典（dict）基于哈希表实现，检查键是否存在的in操作平均时间复杂度为O(1)，最坏情况为O(n)（极端哈希冲突场景），但实际开发中几乎不会触发最坏情况，通常可视为常数级操作。

因此你当前的代码整体时间复杂度为O(m + n)（m为arr1长度，n为arr2长度）：

• 第一个循环遍历arr1，每个元素的in检查与字典插入均为O(1)，总耗时O(m)
• 第二个循环遍历arr2，每个元素的in检查为O(1)，总耗时O(n)
  完全是线性复杂度，不存在你担心的O(n²)问题。

二、更简洁的线性时间实现方案 #

虽然原代码已满足O(n)复杂度，但可以用Python的set（集合）进一步简化——集合同样基于哈希表实现，元素存在性检查为O(1)，且无需维护键值对，更贴合“仅检查存在性”的需求：

arr1 = ["a","b","c","d"]
arr2 = ["x","y","z","c"]

# 将arr1转换为集合，自动完成去重
exist_set = set(arr1)

print(exist_set)

for item in arr2:
    print("true" if item in exist_set else "false")

这段代码的时间复杂度与原代码一致，仍为O(m + n)，但代码更简洁直观，省去了手动维护字典的冗余操作。

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