SortedSet<T> Overlaps方法复杂度存疑：文档与实现不一致？

文档标注的O(n)是错误的，实际该方法的时间复杂度应为O(m * log n)，其中：

• m 是传入的other集合的元素总数
• n 是当前SortedSet<T>实例的元素总数

原因分析 #

1. 从给出的实现代码来看：

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

   方法会遍历other中的每一个元素，对每个元素调用Contains方法。而SortedSet<T>的Contains方法基于红黑树实现，单个元素的查找复杂度是O(log n)。

2. 最坏情况下（两个集合没有交集），需要遍历完other的所有m个元素，每个元素执行一次O(log n)的查找，因此整体复杂度是O(m * log n)。

3. 文档的标注大概率是笔误，混淆了HashSet<T>.Overlaps的复杂度——HashSet的Contains是O(1)平均复杂度，因此它的Overlaps才是O(n)（n为传入集合的元素数）。

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