问题描述
我试图澄清一些关于TreeSet的一些操作的复杂性的事情。在javadoc上它说：
I am trying to clear up some things regarding complexity in some of the operations of TreeSet. On the javadoc it says:
到目前为止一切顺利。我的问题是在addAll（），removeAll（）等上发生了什么。这里的Set的javadoc说：
So far so good. My question is what happens on addAll(), removeAll() etc. Here the javadoc for Set says:
它只是解释了操作的逻辑结果还是提示了复杂性？我的意思是，如果两组由例如红黑树最好以某种方式加入树木，而不是将中的每个元素添加到另一个。
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.
无论如何，有没有办法将两个TreeSet合并为一个具有O（logn）复杂度的树？
In any case, is there a way to combine two TreeSets into one with O(logn) complexity?
提前感谢您。 ： - ）
Thank you in advance. :-)
推荐答案
你可以想象如何将特殊情况优化到 O（log n），但最坏的情况必须是 O（m log n）其中 m 和 n 是每棵树中元素的数量。
You could imagine how it would be possible to optimize special cases to O(log n), but the worst case has got to be O(m log n) where m and n are the number of elements in each tree.
编辑：
描述可以加入的特殊情况算法 O（log（m + n））中的树，但请注意限制： S1 的所有成员必须小于 S2 的所有成员。这就是我的意思，对特殊情况有特殊的优化。
Describes a special case algorithm that can join trees in O(log(m + n)) but note the restriction: all members of S1 must be less than all members of S2. This is what I meant that there are special optimizations for special cases.
这篇关于Java中TreeSet操作的计算复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！