Java中TreeSet操作的计算复杂性？
我试图澄清一些关于TreeSet的一些操作的复杂性的事情。 在javadoc上它说：
“这种实现为基本操作（添加，删除和包含）提供了有保证的log（n）时间成本。”
到现在为止还挺好。 我的问题是在addAll（），removeAll（）等上发生了什么。这里的Set的javadoc说：
“如果指定的集合也是一个集合，则addAll操作会有效地修改此集合，使其值为两个集合的并集。”
它只是解释了操作的逻辑结果还是暗示了复杂性？ 我的意思是，如果两个集合由例如红黑树代表，那么以某种方式加入树木比将“一个”的每个元素“添加”到另一个更好。
在任何情况下，有没有办法将两个TreeSet合并为一个具有O（logn）复杂度的TreeSet？
先谢谢你。 🙂
你可以想象如何将特殊情况优化为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所有成员。 这就是我的意思，对特殊情况有特殊的优化。
查看TreeSet的java源代码，看起来如果传入的集合是SortedSet，那么它使用O（n）时间算法。 否则它会调用super.addAll，我猜这将导致O（n logn）。
编辑 – 猜测我读的代码太快，如果支持映射为空，TreeSet只能使用O（n）算法
根据这篇博文：
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
它是O（n log n）。 由于文档没有提供有关复杂性的提示，因此如果性能对您至关重要，您可能需要编写自己的算法。
不可能像在Disjoint-set数据结构中那样执行树的合并或连接集，因为您不知道2树中的元素是否是不相交的。 由于数据结构具有其他树中内容的知识，因此有必要在添加到另一个树之前检查另一个树中是否存在一个元素，或者至少尝试将其添加到另一个树中，如果发现它则中止添加它方式。 所以，它应该是O（MlogN）