10

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

“此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。”

到现在为止还挺好。我的问题是 addAll()、removeAll() 等会发生什么。这里 Set 的 javadoc 说：

“如果指定的集合也是一个集合，那么 addAll 操作会有效地修改这个集合，使其值是两个集合的并集。”

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

无论如何，有没有办法将两个 TreeSet 组合成一个复杂度为 O(logn) 的树集？

先感谢您。:-)

4

4 回答 4

6

您可以想象如何将特殊情况优化为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。这就是我的意思是针对特殊情况进行特殊优化。

于 2010-08-02T18:07:22.570 回答
3

查看 TreeSet 的 java 源代码，如果传入的集合是 SortedSet，那么它使用 O(n) 时间算法。否则它会调用 super.addAll，我猜这会导致 O(n logn)。

编辑 - 我猜我读代码太快了，如果它的后备图是空的，TreeSet 只能使用 O(n) 算法

于 2010-08-02T18:11:56.393 回答
2

根据这篇博文：
http
://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html 它是 O(n log n)。由于文档没有提供有关复杂性的提示，因此如果性能对您至关重要，您可能需要编写自己的算法。

于 2010-08-02T18:07:36.720 回答
0

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)

于 2010-08-02T18:14:18.580 回答