在计算大O复杂度时感到困惑

Question

最近，我开始用Python学习数据结构。

list_ = [6, 4, 3, 2, 1, 7]
expected_sum_result = 9

def two_pair_sum_using_complement(array, expected_sum):
    unique_numbers = set()  #set
    for num in array:
        if num in unique_numbers:
            return True
        unique_numbers.add(expected_sum - num)
        print(unique_numbers)
    return False


print(
 two_pair_sum_using_complement(array=list_, expected_sum=expected_sum_result))

在上面的代码中，你可以简单地说它的复杂度是O(n)，但是我有一个疑问，就是我用了“if num in unique_numbers”这个操作符，它的复杂度也是O(n)，我参考了这个网站 https://wiki.python.org/moin/TimeComplexity，并附上了截图。

那么，我可以认为我有一个O(n)的FOR循环，而在这个FOR循环里面又有一个O(n)的in操作符，所以整体的复杂度是O(n^2)吗？

我尝试过用一些网站和AI来理解这些内容，但我还是觉得很难。

Answer 1

在Python中，集合（set）通常是通过一种叫做哈希表的数据结构来实现的。
这种数据结构在最坏的情况下查找一个值可能需要O(n)的时间，但在平均情况下只需要O(1)。
简单来说，这种结构就像是有一组“桶”，每个值会通过一个哈希函数来决定放进哪个桶里。
当值在这些桶中分布得比较均匀时，就会出现平均情况。想了解更多，可以查看上面的链接。

这和你提到的页面上的信息是一致的：

总结一下：

由于你的代码中有一个线性循环，并且每次迭代都要查找集合，所以在最坏情况下，整体复杂度是O(n²)，但在平均情况下是O(n)。

需要注意的是，上面的分析没有考虑print语句，因为它并不算是算法的一部分。