Java中TreeSet操作的计算复杂性？

Question

我试图澄清一些关于TreeSet的一些操作的复杂性的事情.在javadoc上它说:

"这种实现为基本操作(添加,删除和包含)提供了有保证的log(n)时间成本."

到现在为止还挺好.我的问题是在addAll(),removeAll()等上发生了什么.这里的Set的javadoc说:

"如果指定的集合也是一个集合,则addAll操作会有效地修改此集合,使其值为两个集合的并集."

它只是解释了操作的逻辑结果还是暗示了复杂性？我的意思是,如果这两个集合由例如红黑树代表,那么以某种方式加入树木比将"一个"的每个元素"添加"到另一个更好.

在任何情况下,有没有办法将两个TreeSet合并为一个具有O(logn)复杂度的TreeSet？

先感谢您.:-)

Answer 1

你能想象它怎么会是可以优化的特殊情况来O(log n),但最坏的情况一定是O(m log n)哪里m和n在每个树元素的数量.

编辑:

描述了一个可以连接树的特殊情况算法,O(log(m + n))但请注意限制:所有成员S1必须少于所有成员S2.这就是我的意思,对特殊情况有特殊的优化.