代码之家 › 专栏 › 技术社区 › Andrey Taptunov

添加到sortedset<t>及其复杂性

sortedset time-complexity c#

23

Andrey Taptunov · 技术社区 · 14 年前

如果count小于内部数组的容量,则此方法是O(1)操作。

有人能解释一下“怎么会这样吗”?我的意思是,当添加新值时,我们需要找到一个正确的地方来添加值(将其与其他值进行比较),并且内部实现看起来像一个具有O(log n)插入复杂性的“红黑树”。

1 回复 | 直到 7 年前

1

28

Hans Passant 14 年前

这个评论完全是错误的。是的,它是一个红黑树,O(log(n))用于插入。通过使用reflector进行查看可以证明这一点,private addifnotpresent()方法包含一个while()循环,使用普通的红黑节点遍历来查找插入点。

这个文档错误已经 been submitted 你知道谁。