set() 函数算法和"&"运算符一起使用时的复杂性

Question

我想计算给定大小n的代码行(用于在两个数组中查找公共元素)的big-o，但我不知道set在Python中是如何工作的。还有它们之间的"&"运算符。有人能帮我了解他们到底是做什么的吗？

result = set(arr1) & set(arr2)

Answer 1

给定两个集合s1和s2，&算子平均为O(min(len(s1), len(s2))

&运算符计算两个集合之间的交集。这意味着结果集将仅具有来自s1和s2两者的元素。

例如：

{1, 2, 3, 4} & {3, 4, 5}

输出：

{3, 4}

操作大致等于：

def intersection(s1, s2):
# make s1 the smaller set no matter what
if len(s1) > len(s2): s1, s2 = s2, s1
res = set()
# iterate over all items in the smaller set and add if they are common to both sets
for item in s1:
if item in s2: res.add(item)
return res

这种时间复杂性来源于以下内容。要构建结果集，必须对其中一个集合中的每个元素进行迭代，并检查该元素是否在另一个集合内。

对一个集合中的所有元素进行迭代是O(N)，而in操作的平均值是O(1)，从而产生总体O(N)运行时。

由于您迭代的集合实际上并不重要，python通过迭代较小的集合来节省一些时间，使O(N)中的N尽可能小，从而导致O(min(len(s1), len(s2))的复杂性。

请注意，这只是案件的平均复杂性。如果集合中的每个元素都以某种方式具有相同的散列，则in操作的最坏(但极为罕见)情况复杂性是O(N)。这将使&操作成为O(len(s1) * len(s2))复杂度的最坏情况