根据MicrosoftDocs，为什么SortedDictionary.GetEnumerator()是C#中的O(logn)操作？
c#
根据Microsoft Doc，该SortedDictionary.GetEnumerator()方法是 C# 中的 O(log n) 操作。SortedDictionary由SortedSet. 查看.NET 源代码行 1911 到 1923，当GetEnumerator()调用该方法时，会实例化一个新的 Enumerator，它会在Stack<T>内部创建一个。然后Stack<T>在 Initialize() 方法中填写。这是一个 O(n) 操作，而不是 O(log n)！
如果有人解释 O(log n) 的原因，我将不胜感激。
回答
Stack 是在 Initialize() 方法中填充的。这是一个 O(n) 操作，而不是 O(log n)！
不，不是真的。该Stack<T>集合仅填充到表示排序数据的二叉树的最深级别。该Initialize()方法遍历二叉树，将数据节点压入堆栈，直到到达枚举器将返回的第一个节点。
二叉树的深度是log n，该Initialize()方法在树的每一层只循环一次，所以循环的代价也是O(log n)。就像文档说的那样。
枚举集合的总成本为 O(n)，但简单地初始化枚举器仅为 O(log n)。
THE END
二维码