为何该算法最坏时间复杂度为O(n)？是否应为O(n²)？

你的误区在于把Python里set的实现当成了普通线性结构（比如列表），实际上两者的底层逻辑完全不同：

• Python的set是哈希表实现的：哈希表的核心是通过哈希函数直接定位元素的存储位置，所以in（检查元素是否存在）和add（添加元素）操作，在平均情况下时间复杂度都是O(1)，根本不需要遍历整个集合。

• 你想象的O(n²)场景不会发生：如果是用列表来存元素，每次检查是否存在确实要遍历当前列表的所有元素，最坏情况下（所有元素都不同）总操作次数是1+2+...+n = O(n²)。但set的哈希表结构避免了这种线性遍历，每个元素的检查和添加都是常数时间级别的操作。

• 关于极端哈希冲突的说明：理论上如果所有元素的哈希值完全相同（极端冲突），哈希表的操作会退化为O(n)，但这种情况在实际中几乎不可能出现——Python的哈希函数设计会尽量分散元素的哈希值，而且哈希表会动态扩容、调整桶的数量来减少冲突概率。算法分析中，我们通常用平均情况时间复杂度来衡量这类哈希表相关算法，也就是O(n)，这也是实际运行中你会看到的表现。

对应到给出的代码：循环遍历数组的n个元素，每个元素的检查和添加操作都是O(1)平均时间，所以整个算法的时间复杂度是O(n)。

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