遍历子集成员测试：字典与列表的时间复杂度对比及正确性验证

你的理解完全正确！用字典（或者更贴合场景的Python集合）来做成员存在性检查，确实比列表高效得多，尤其是当集合A的规模变大时，这种性能差异会非常显著。

两段代码的效率分析 #

Code 1（列表实现） #

这段代码里，每次执行i in A时，Python会逐个遍历列表A的元素，直到找到匹配项或者遍历完整个列表。单次检查的最坏时间复杂度是O(|A|)，而整个循环要执行|B|次，所以总时间复杂度是O(|B| × |A|)。

A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]
for i in B:
    if i in A:
        print(i)
    else:
        print(-1)

Code 2（字典实现） #

这里我们先把列表A转换成字典的键（值用0填充，其实值是什么不影响查找）。Python的字典基于哈希表实现，所以i in A_dict的最坏时间复杂度是O(1)（平均情况也是O(1)）。整个流程的总时间复杂度是O(|A| + |B|)：其中O(|A|)是构建字典的开销，O(|B|)是遍历B做检查的开销。当|B|远大于|A|时，构建字典的成本几乎可以忽略，整体复杂度趋近于O(|B|)。

A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]
A_dict = {}
for i in A:
    A_dict[i] = 0
for i in B:
    if i in A_dict:
        print(i)
    else:
        print(-1)

关于时间复杂度判断的验证 #

你对两段代码的复杂度判断基本准确，唯一需要补充的是Code2的总复杂度是O(|A| + |B|)，不过当|B|远大于|A|时，O(|A|)的部分可以忽略，说它趋近于O(|B|)是完全没问题的。而Code1的O(|B|×|A|)是准确的，当A的长度增长时，这个复杂度会急剧上升——比如如果A有1000个元素，B有10000个元素，Code1要做1000×10000=10,000,000次比较，而Code2只需要1000+10000=11,000次操作，差距一目了然。

额外小建议 #

在Python中，如果你只是需要做成员存在性检查，用set（集合）会比字典更简洁，因为集合本身就是专门为快速成员查找设计的，不需要额外存储键值对：

A = {1, 2, 3}  # 直接定义为集合
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]
for i in B:
    print(i if i in A else -1)

这段代码的效率和字典实现几乎一致，但代码更简洁，语义也更清晰——明确表达了我们只关心元素是否在集合中，不需要关联任何值。

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