Rechnerische Komplexität von TreeSet-Operationen in Java?

Question

Ich versuche einige Dinge in Bezug auf Komplexität in einigen der Operationen von TreeSet zu klären. Auf der javadoc heißt es:

"Diese Implementierung garantiert log (n) Zeitaufwand für die grundlegenden Operationen (Hinzufügen, Entfernen und enthält) zur Verfügung stellt."

So weit so gut. Meine Frage ist, was auf addAll geschieht(), removeAll() usw. Hier ist die javadoc für Set sagt:

„Wenn die angegebene Sammlung ist auch ein Satz, der addAll Betrieb effektiv diesen Satz modifiziert, so dass sein Wert ist die Vereinigung der beiden Sets. "

Erklärt es nur das logische Ergebnis der Operation oder gibt es einen Hinweis auf die Komplexität? Ich meine, wenn die zwei Mengen durch z.B. rot-schwarze Bäume wäre es besser, irgendwie die Bäume zu verbinden, als jedes Element von einem zum anderen "hinzuzufügen".

Gibt es in jedem Fall eine Möglichkeit, zwei TreeSets zu einem mit O (logn) Komplexität zu kombinieren?

Vielen Dank im Voraus. :-)

Answer 1

Man könnte sich vorstellen, wie es möglich wäre, Sonderfälle zu O(log n), aber der schlimmste Fall bekam zu sein hat zu optimieren, wo m und n die Anzahl der Elemente in jedem Baum sind.

Edit:

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

einen Sonderfall Algorithmus beschreibt, dass Bäume in O(log(m + n)) aber beachten Sie die Einschränkung teilnehmen können: alle Mitglieder der S1 muss kleiner sein als alle Mitglieder der S2. Das heißt, dass es spezielle Optimierungen für Spezialfälle gibt.

Answer 2

Nach diesem Blog-Eintrag:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
es ist O (n log n). Da die Dokumentation keine Hinweise auf die Komplexität gibt, möchten Sie möglicherweise einen eigenen Algorithmus schreiben, wenn die Leistung für Sie von entscheidender Bedeutung ist.

Answer 3

Betrachtet man die Java-Quelle für TreeSet, sieht es so aus, wenn die übergebene Auflistung ein SortedSet ist, dann wird ein O (n) -Zeitalgorithmus verwendet. Ansonsten wird super.addAll aufgerufen, was, wie ich vermute, zu O (n logn) führt.

EDIT - ich denke, der Code zu schnell, TreeSet lesen nur die O verwenden können (n) Algorithmus, wenn es ist nicht möglich auszuführen Verschmelzung von Bäumen oder verbinden Sätze wie in Disjoint- Karte leer ist

Answer 4

Rückendeckung Setzen Sie Datenstrukturen, weil Sie nicht wissen, ob die Elemente in den zwei Bäumen disjunkt sind. Da die Datenstrukturen Wissen über den Inhalt in anderen Bäumen haben, ist es notwendig, zu prüfen, ob ein Element in dem anderen Baum existiert, bevor es hinzugefügt wird oder zumindest versucht wird, es in einen anderen Baum einzufügen und es hinzuzufügen, wenn Sie es finden der Weg. So sollte es sein O (MlogN)