关于Python两数之和代码的Big O时间复杂度计算疑惑

你的代码时间复杂度确实是O(n)，核心原因在于Python中set的in成员检查和add操作的平均时间复杂度为O(1)，而非你担心的O(n)。

关键原理：Python集合的底层实现 #

Python的set基于哈希表（Hash Table）实现，哈希表的核心特性是通过哈希函数直接计算元素的存储位置，因此：

• 执行num in unique_numbers时，不需要遍历整个集合，而是通过哈希值直接定位元素是否存在，平均情况下只需常数时间。
• unique_numbers.add(expected_sum - num)操作同理，也是通过哈希值定位存储位置，平均时间复杂度O(1)。

复杂度计算 #

外层for循环的时间复杂度是O(n)（n为输入数组的长度），循环内的每一步操作都是O(1)，因此总时间复杂度为O(n) × O(1) = O(n)。

补充说明：最坏情况的例外 #

哈希表在极端情况下（比如所有元素的哈希值都相同，出现严重哈希冲突），in和add操作会退化为O(n)，但这种情况在实际场景中极少出现，算法时间复杂度分析通常以平均情况为准，所以你的代码仍被认为是O(n)复杂度。

对比：列表与集合的in操作差异 #

如果把代码中的set换成list，那么num in unique_numbers的时间复杂度就是O(n)，此时总复杂度才会变成O(n²)——这也是你产生疑惑的可能原因，但集合的实现逻辑和列表完全不同。

你的代码执行流程示例 #

以输入list_ = [6, 4, 3, 2, 1, 7]、expected_sum_result = 9为例：

• 第一次循环：num=6，检查6不在空集合，添加9-6=3，集合变为{3}
• 第二次循环：num=4，检查4不在{3}，添加9-4=5，集合变为{3,5}
• 第三次循环：num=3，检查3在集合中，直接返回True，循环终止

整个过程仅执行3次循环，每次操作都是常数时间，直观体现了O(n)的效率。

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