我正在嘗試清除有關TreeSet某些操作的複雜性的一些事情。在javadoc的，它說：Java中TreeSet操作的計算複雜性？
「此實現提供了 基本操作（添加，刪除和 含） 保證的log（n）的時間成本。」
到目前爲止好。我的問題是關於中的addAll（）的removeAll（）等會發生什麼這裏設置的javadoc說：
「如果指定集合也是一個 集，則addAll操作有效 修改這一套使得其值是 這兩套的結合。「
它只是解釋操作的邏輯結果，還是提示覆雜性？我的意思是，如果兩組由例如紅黑樹，以某種方式加入樹比將另一個元素的「每個元素」「添加」更好。
在任何情況下，有沒有辦法將兩個TreeSet合併成一個O（logn）複雜度？
預先感謝您。 :-)
你可以想象這將是多麼有可能優化特殊情況下O(log n)，但最壞的情況下一定是其中m和n在每個樹元素的數量。
編輯：
http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm
描述一個特殊情況的算法，可以加入樹木O(log(m + n))但要注意的限制：的S1所有成員必須小於S2所有成員。這就是我的意思是對特殊情況有特殊的優化。
根據這一博客帖子：
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
這是爲O（n log n）的。由於文檔沒有提供關於複雜性的提示，如果性能對您至關重要，您可能需要編寫自己的算法。
查看TreeSet的Java源代碼，它看起來像是如果集合中傳入的是SortedSet，那麼它使用O（n）時間算法。否則它會調用super.addAll，我猜測會導致O（n logn）。
編輯 - 想我讀碼速度過快，如果它支持映射爲空TreeSet中只能使用O（n）的算法
這是不可能的樹木進行合併或加入組像Disjoint-設置數據結構，因爲您不知道2棵樹中的元素是否不相交。由於數據結構具有關於其他樹中內容的知識，因此有必要在添加到其他樹之前檢查其他樹中是否存在一個元素，或者至少嘗試將其添加到另一個樹中，並在發現它時中止添加它方式。 因此，它應該是O（MlogN）
我不太明白這一點。假設您有兩個沒有重疊元素並由紅黑樹表示的SortedSet。因爲在紅黑樹中的「加入」操作需要O（log（n + m））時間，所以你不能加入它們？ – 2010-08-02 18:34:19
給定2個任意TreeSets，你將如何知道是否是這種情況？ – user855 2010-08-02 18:36:51
那麼根據我目前正在製作的程序，我可以保證兩個TreeSet不會有任何重疊的元素。然而，正如其餘答案所指出的那樣，我似乎無法將它們加入到O（log（n + m））中。 – 2010-08-02 18:50:33
回覆我得到的答案： 我不太明白這一點。假設您有兩個沒有重疊元素並由紅黑樹表示的SortedSet。因爲在紅黑樹中的「加入」操作需要O（log（n + m））時間，所以你不能加入它們？ – 2010-08-02 18:35:23