Java中TreeSet操作的计算复杂性？ [英] Computational complexity of TreeSet operations in Java?

问题描述

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

I am trying to clear up some things regarding complexity in some of the operations of TreeSet. On the javadoc it says:

此实现为
基本提供
保证log（n）时间成本操作（添加，删除和
包含）。

"This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains)."

到目前为止一切顺利。我的问题是在addAll（），removeAll（）等上发生了什么。这里的Set的javadoc说：

So far so good. My question is what happens on addAll(), removeAll() etc. Here the javadoc for Set says:

如果指定的集合是另外一个
设置，addAll操作有效
修改这个集合，使它的值为
这两个集合的联合。

"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.

无论如何，有没有办法将两个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.

编辑：

http：/ /net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

描述可以加入的特殊情况算法 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操作的计算复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！