为什么 SortedDictionary<K, V>.GetEnumerator 是 O(log n)，但 SortedSet<T>.GetEnumerator 是 O(1)？

Question

根据SortedSet<T>.GetEnumerator文档：

 

此方法是O(1)操作。

根据SortedDictionary<K, V>.GetEnumerator文档：

 

此方法是O(log n)操作，其中n是计数。

考虑到SortedDictionary<K，V>在内部被实现为SortedSet<KeyValuePair<K，V>，这两个陈述是否都可以成立呢？我检查了SortedDictionary类的GetEnumerator代码-它直接使用SortedSet的枚举器。我注意到SortedSet的枚举器实现并且它似乎具有O(log n)的特性（这是代码）：

public SortedSet<T>.Enumerator GetEnumerator()
{
  return new SortedSet<T>.Enumerator(this);
}

//which calls this constructor:
internal Enumerator(SortedSet<T> set)
{
  this.tree = set;
  this.tree.VersionCheck();
  this.version = this.tree.version;
  this.stack = new Stack<SortedSet<T>.Node>(2 * SortedSet<T>.log2(set.Count + 1));
  this.current = (SortedSet<T>.Node) null;
  this.reverse = false;
  this.siInfo = (SerializationInfo) null;
  this.Intialize();
}

private void Intialize()
{
  this.current = (SortedSet<T>.Node) null;
  SortedSet<T>.Node node1 = this.tree.root;
  while (node1 != null)
  {
    SortedSet<T>.Node node2 = this.reverse ? node1.Right : node1.Left;
    SortedSet<T>.Node node3 = this.reverse ? node1.Left : node1.Right;
    if (this.tree.IsWithinRange(node1.Item))
    {
      this.stack.Push(node1);
      node1 = node2;
    }
    else
      node1 = node2 == null || !this.tree.IsWithinRange(node2.Item) ? node3 : node2;
  }
}

这难道不意味着文档有误，SortedSet<T>.GetEnumerator的时间复杂度是O(log n)吗？ 关于GetEnumerator调用的性能并没有太多说明，只是确保我理解正确。

- nawfal

---

看起来这肯定是文档错误。 - Jon

你需要检查 SortedDictionary 的代码来看看发生了什么。它是否调用了 SortedSet log(n) 次？如果是这样，那么文档是正确的。 - user2880486

@user2880486 SortedDictionary 直接调用 SortedSet 枚举器。因为内部实现是 SortedSet<KeyValuePair<K,V>>。它不会调用枚举器 log n 次。此外，我的问题不是 SortedDictionary 是 O(logn)，而是 SortedSet 是 O(1)。这就是为什么我只发布了 SortedSet 枚举器的代码。从代码来看，它似乎不是 O(1)，而是 O(logn)。 - nawfal

感谢您发送有关我们在 MSDN 上的主题的反馈。我已经在我们的最新文档版本中修复了文档错误。不幸的是，我无法修复相同主题的 4.0 版本。 - Maíra Wenzel - MSFT

Answer 1

我完全同意你的观点。

SortedSet 内部使用红黑树结构，保证平衡 (Wikipedia; Red-Black Trees, R. Sedgewick, Princeton University)。因此，高度受到 2 * log2(n + 1) 的限制。即使在 SortedSet.cs 中的一个 代码注释 中也指出了这一点，并且枚举器堆栈的大小也相应地设置。

准备堆栈的 while 循环在初始化和进行 (MoveNext) 枚举器时都是 O(log n)。

有关此讨论的MSDN 文档的反馈已提交。

更新：

今天微软终于更新了文档。对于 4.0 版本，它仍然声明这是一个 O(1) 操作。虽然我对此表示怀疑，但可以接受。

- Peopleware

---

今天微软终于更新了文档。对于4.0版本，它仍然声明这是一个O(1)操作。虽然我有所怀疑，但我可以接受这个说法。 - Peopleware