对于集合 S 和 T，为什么 Python 的 S -= T 采用 O(len(T)) 而不是 O(len(S))？

Question

this Python time complexity table 中的 Set 条目说，下面的评论证实，S.difference_update(T) 需要时间 O(len(T)) 而 S - T 需要 O(len(S) ).给出的原因是第一个的算法是"for every element in T remove it from S"，而第二个的算法是"for every element in S add it to the new set, if not in T".

算法 "for every element in S, remove it from S if it's in T" 会不会工作得很好并且是 O(len(S))？为什么不只选择较短的那个呢？

我想我没看到什么。

Answer 1

从技术上讲，在操作中并没有真正要求 S 大于 T。很可能 T 实际上比 S 大得多：

>>> S = {1, 2, 3}
>>> T = {3, 4, 5, 6, 7, 8, 9}
>>> S - T
{1, 2}

因此，为所有操作选择一个或另一个算法将是一个任意选择，因为您根本不知道哪个实际上更短（如果您不知道集合）。

但总的来说，这并不重要。 S 和 T 都是输入，O(|T|) 和 O(|S|) 仍然是 O(n)，即线性。所以这根本不是问题。

我已经与 the source 核实，以进一步验证到底发生了什么。

S.difference(T),S - T(set_difference)：计算两个集合对象的差值。它遍历 S 中的元素并检查每个元素是否包含在 T 中。如果不包含，则将其添加到结果集中。

如果 S 比 T 大得多，实现实际上复制 S 并执行 S' -= T。由于这会在 S 中留下很多项目，因此它比从空集开始并不断添加 S 中的元素更便宜。
S.difference_update(T) (set_difference_update)：首先，它接受多个参数。所以从技术上讲，它不能检查 T 的长度并简单地交换，因为周围有多个 T。更重要的是，它支持本身不是集合的 T（任何可迭代对象），因此它只能通过迭代这些可迭代对象并从集合中删除这些项目来工作。

所以为此，迭代 S 实际上是不可能的（因为我们在 Ts 中没有常量成员检查）。

因此，事实证明，发生这种情况是有原因的。这些原因大多隐藏在实际的 set 方法中，而不是运算符实现中（虽然在内部使用这些方法）。虽然你可以进一步微优化一些特殊情况，如上所述，但这不会给你带来太多改进，尽管从技术上讲，你仍然保持 O(n)。而在通常的应用中（尤其是Python），这样的操作不太可能成为你的瓶颈。

对于集合 S 和 T，为什么 Python 的 S -= T 采用 O(len(T)) 而不是 O(len(S))？

For sets S and T, why does Python's S -= T take O(len(T)) and not O(len(S))?

python

big-o

python-internals