c# - 根据 Microsoft Docs，为什么 SortedDictionary.GetEnumerator() 是 C# 中的 O(log n) 操作？

Question

根据Microsoft Doc ，SortedDictionary.GetEnumerator()方法在 C# 中是 O(log n) 操作。 SortedDictionary由 SortedSet 支持。正在查看.NET source第 1911 行到 1923 行，当 GetEnumerator()方法被调用，一个新的枚举器被实例化，它创建一个 Stack<T>内部。然后是Stack<T>填充在Initialize()方法中。这是一个 O(n) 操作，而不是 O(log n)!

如果有人解释 O(log n) 的原因，我将不胜感激。

Answer 1

the Stack is filled in in the Initialize() method. This is an O(n) operation, not O(log n)!

不，不是真的。 Stack<T>集合仅填充到表示排序数据的二叉树的最深级别。 Initialize()方法遍历二叉树，将数据节点压入堆栈，直到到达枚举器将返回的第一个节点。

二叉树的深度为log n，Initialize()方法在树的每一层仅循环一次，因此循环成本也是 O(log n)。就像文档所说的那样。

枚举集合的总体成本将为 O(n)，但简单地初始化枚举器仅为 O(log n)。