为何C#中SortedDictionary.GetEnumerator()按微软文档是O(log n)操作？

关于SortedDictionary.GetEnumerator()复杂度的说明 #

你对复杂度的误解核心来源于两个认知偏差：

• 首先要区分**GetEnumerator()方法单次调用的复杂度和遍历整个集合的总复杂度**，微软文档标注的是前者的时间成本。
• SortedDictionary 底层依赖的 SortedSet 采用红黑树实现，红黑树的树高稳定为O(log n)。你提到的枚举器初始化阶段填充Stack<T>的操作，并不是遍历整棵树压入所有节点，而是仅沿着红黑树的最左路径，从根节点开始依次压入路径上的节点，直到最左的叶子节点为止。这个过程压入栈的节点数量刚好等于树的高度，所以复杂度天然为O(log n)，并非你误以为的O(n)。

后续遍历阶段的开销不属于GetEnumerator()的调用成本：每次调用MoveNext()时会弹出栈顶节点返回，再将该节点右子树的最左路径依次压入栈，每个节点只会入栈、出栈各一次，因此遍历整个集合的总复杂度是O(n)，和初始化阶段的开销并不冲突。

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