MSDN指出以下SortedSet(T).Add方法:
如果Count小于内部数组的容量,则此方法是O(1)操作。
有人能解释一下"怎么做"吗?我的意思是,当添加新值时,我们需要找到一个正确的位置来添加一个值(与另一个值进行比较),而内部实现看起来像是一个具有O(log N)插入复杂度的"红-黑树"。
MSDN指出以下SortedSet(T).Add方法:
如果Count小于内部数组的容量,则此方法是O(1)操作。
有人能解释一下"怎么做"吗?我的意思是,当添加新值时,我们需要找到一个正确的位置来添加一个值(与另一个值进行比较),而内部实现看起来像是一个具有O(log N)插入复杂度的"红-黑树"。
这个评论是错误的。没错,它是一棵红黑树,在插入时的时间复杂度为O(log(n))。通过使用Reflector查看代码证实了这一点,私有的AddIfNotPresent()方法包含一个while()循环来查找插入点,使用普通的红黑节点遍历。
你知道的那个人已经提交了这个文档错误的bug反馈。
SortedSet<T>(IEnumerable<T>)
的文档中得到了确认,文档指出其复杂度为 O(n log(n))。 - Numid