Java 中 TreeSet 操作的计算复杂度？
我试图澄清一些有关 TreeSet 某些操作的复杂性的事情。在 javadoc 上它说：
“此实现提供 保证 log(n) 时间成本 基本操作（添加、删除和 包含）。”
到目前为止一切顺利。我的问题是 addAll()、removeAll() 等会发生什么。这里 Set 的 javadoc 说：
“如果指定的集合也是 set、addAll操作有效 修改该集合，使其值为 两个集合的并集。”
它只是解释操作的逻辑结果还是给出了有关复杂性的提示？我的意思是，如果这两个集合由例如红黑树表示，那么最好以某种方式加入 树
无论如何，有没有一种方法可以将两个 TreeSet 组合成一个复杂度为 O(logn) 的
？提前谢谢您。
I am trying to clear up some things regarding complexity in some of the operations of TreeSet. On the javadoc it says:
"This implementation provides
guaranteed log(n) time cost for the
basic operations (add, remove and
contains)."
So far so good. My question is what happens on addAll(), removeAll() etc. Here the javadoc for Set says:
"If the specified collection is also a
set, the addAll operation effectively
modifies this set so that its value is
the union of the two sets."
Is it just explaining the logical outcome of the operation or is it giving a hint about the complexity? I mean, if the two sets are represented by e.g. red-black trees it would be better to somehow join the trees than to "add" each element of one to the other.
In any case, is there a way to combine two TreeSets into one with O(logn) complexity?
Thank you in advance. :-)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以想象如何将特殊情况优化为
O(log n)，但最坏的情况必须是O(m log n)其中m和n是每棵树中的元素数量。编辑：
http://net.pku.edu .cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm
描述一种特殊情况的算法，可以在
O(log(m + n))中连接树，但请注意限制：S1的所有成员必须小于S2的所有成员。这就是我的意思，特殊情况有特殊优化。You could imagine how it would be possible to optimize special cases to
O(log n), but the worst case has got to beO(m log n)wheremandnare the number of elements in each tree.Edit:
http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm
Describes a special case algorithm that can join trees in
O(log(m + n))but note the restriction: all members ofS1must be less than all members ofS2. This is what I meant that there are special optimizations for special cases.查看TreeSet的java源代码，看起来如果传入的集合是SortedSet，那么它使用O(n)时间算法。否则它会调用 super.addAll，我猜这将导致 O(n logn)。
编辑 - 猜我读代码太快了，TreeSet 只能使用 O(n) 算法，如果它的支持映射是空的
Looking at the java source for TreeSet, it looks like it if the passed in collection is a SortedSet then it uses a O(n) time algorithm. Otherwise it calls super.addAll, which I'm guessing will result in O(n logn).
EDIT - guess I read the code too fast, TreeSet can only use the O(n) algorithm if it's backing map is empty
根据这篇博文：
http://rgrig.blogspot.com/2008/06/ java-api-complexity-guarantees.html
是 O(n log n)。由于文档没有给出有关复杂性的提示，因此如果性能对您来说至关重要，您可能需要编写自己的算法。
According to this blog post:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
it's O(n log n). Because the documentation gives no hints about the complexity, you might want to write your own algorithm if the performance is critical for you.
无法像不相交集数据结构那样执行树的合并或连接集，因为您不知道两棵树中的元素是否不相交。由于数据结构了解其他树中的内容，因此有必要在添加到另一棵树之前检查一个元素是否存在于另一棵树中，或者至少尝试将其添加到另一棵树中，如果在上找到它，则中止添加它道路。
所以，它应该是 O(MlogN)
It is not possible to perform merging of trees or join sets like in Disjoint-set data structures because you don't know if the elements in the 2 trees are disjoint. Since the data structures have knowledge about the content in other trees, it is necessary to check if one element exists in the other tree before adding to it or at-least trying to add it into another tree and abort adding it if you find it on the way.
So, it should be O(MlogN)