重叠 SortedSet<T> 的复杂度

Question

在Microsoft 文档中，复杂度被表示为O(n)。

但如果你看实现的话，

  foreach (T item in other)
            {
                if (Contains(item))
                {
                    return true;
                }
            }

如果对每个元素都调用搜索方法，那么复杂度为O(m*log(n))。那到底谁是对的呢？

- Men

---

对于HashMaps，Contains是O(1)操作，而迭代数组中的每个项是O(n)。将两者结合起来得到O(n)。 - Cihan Yakar

@CihanYakar，您能否澄清一下您评论中的HashMap来自哪里？我没有看到任何关于SortedSet的Contains是O(1)的迹象（至少不在代码或文档中，文档中说是O(log(n))... - Alexei Levenkov

我认为文档中有错误。 - Charlieface

@CihanYakar，不是的，它不是O(1)。 - Zazaeil

@AlexeiLevenkov 不知怎么的，我以为是 HashSet<T> 的 contains 是 O(1)。但你完全正确，因为 SortedSet 的 contains 复杂度不同。谢谢！ - Cihan Yakar

Answer 1

这是文档中的错误，如果你查看Contains（以及使用FindNode实现它），你会看到：

这个方法的时间复杂度是O(log n)。

这使得Overlaps的时间复杂度为O(n log m)，其中m是"this"集合中的元素数量，n是other中的元素数量。

为文档创建了PR。

更新

PR已合并，现在文档上说：

该方法是一个 O(n log m) 的操作，其中 m 是 Count，n 是 other 中元素的数量。

- Guru Stron

Answer 2

你是正确的。文档是错误的。

类似于 IsSubsetOf 的方法利用 O(1) 的 GetViewBetween 方法来实现对具有相同相等比较器的两个 SortedSets 进行比较时的 O(n) 复杂度。

Overlaps 还有逻辑来优化这种情况，如果两个集合的最小值和最大值证明它们根本不会重叠，则将其变为O(1)操作。理论上，与具有重叠范围的另一个排序集相比，Overlaps 可以应用额外的优化，使其成为O(n)，但它没有这样做。

在所有其他情况下，正如你所指出的那样，Overlap 会使用一个循环和 Contains 检查，而 Contains 是一个 O(log n) 操作, 使得循环（平均而言，假设有许多不匹配的值）为 O(n * log m)，其中 n 是另一个集合中的数量，m 是此集合中的数量。

- StriplingWarrior