MSDN指出以下SortedSet(T).Add方法:
如果Count小于内部数组的容量，则此方法是O(1)操作。
有人能解释一下"怎么做"吗？我的意思是，当添加新值时，我们需要找到一个正确的位置来添加一个值（与另一个值进行比较），而内部实现看起来像是一个具有O（log N）插入复杂度的"红-黑树"。
向 SortedSet<T> 添加元素及其复杂度
36
- Andrey Taptunov
1
自那时以来，他们已经对其进行了更改。 - nawfal
1个回答
40
这个评论是错误的。没错，它是一棵红黑树，在插入时的时间复杂度为O(log(n))。通过使用Reflector查看代码证实了这一点，私有的AddIfNotPresent()方法包含一个while()循环来查找插入点，使用普通的红黑节点遍历。
你知道的那个人已经提交了这个文档错误的bug反馈。
- Hans Passant
2
4知悉，链接已失效。 - Daniel
2这一点在
SortedSet<T>(IEnumerable<T>) 的文档中得到了确认，文档指出其复杂度为 O(n log(n))。 - Numid网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接