Laufzeitkomplexität | sortieren mit Binärbaum

[DaKa]

Hallo,

da ihr mir beim letzten Mal schon so schnell und kompetent weitergeholfen habt, hoffe ich hier nochmal auf Unterstützung:

gegeben:

• unsortierte Menge M mit n Elementen
  

verwendetes Sortierverfahren:

• Aufbau eines binären Suchbaums
  
• Inorderdurchlauf dieses Baumes
  

Gefragt:

• Laufzeitkomplexität (best- und worst-case)
  

########################

ANSATZ:

• AUFBAU: Suche die Stelle, an der es eingefügt werden soll hat Laufzeitkomplexität O(log n) im worst-case und O(1) im best-case, das einfügen selber O(1) [--> stimmt das?]
  
• INORDERDURCHLAUF: die Laufzeitkomplexität für den best- und worst-case ist O(n), da jeweils alle Elemente durchlaufen werden müssen, um sie sortiert ausgeben zu können [--> stimmt das?]
  

daraus erhielte ich dann folgende Gleichungen (AUFBAU[=suchen+einfügen]+DURCHLAUF):

• best-case: (O(1)+O(1)+O(n)
  
• worst-case: (O(log n)+O(1)+O(n)
  

Stimmt der Ansatz überhaupt und wenn ja, wie lautet dann die Laufzeitkomplexität, also wie könnte man das auflösen.

Danke für Eure Mühen,

Viele Grüße

[flashpixx]

AUFBAU: Suche die Stelle, an der es eingefügt werden soll hat Laufzeitkomplexität O(log n) im worst-case und O(1) im best-case, das einfügen selber O(1) [--> stimmt das?]

Das kannst Du so pauschal nicht sagen, denn das kommt darauf an wie Deine Datenstrukturen aussehen. Man kann gerade Binärbäume als Arraysstrukturen speichern, wobei man dann die Positionen des nächsten Knotens direkt berechnen kann (siehe Ein Speichermodell der Informatik).

Auch kommt es darauf an, ob Du z.B. eine einzelne Ebene des Baums noch zwischen den Blättern vernetzt, so kannst Du Dir z.B. das Suchen von der Wurzel abhängig sparen.

[*]INORDERDURCHLAUF: die Laufzeitkomplexität für den best- und worst-case ist O(n), da jeweils alle Elemente durchlaufen werden müssen, um sie sortiert ausgeben zu können [--> stimmt das?]

Ja kann sein, kommt aber letztendlich auf die darunterliegende Datenstruktur an. O(n) passt, wenn man davon ausgeht, dass Du ein Array für die Daten hast.

Der Worst-Case ist meistens der einfachste Fall (http://de.wikipedia.org/wiki/Binärer_Suchbaum bzw http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29 ). Je nachdem ob Dein Baum z.B. ausbalanciert funktionieren entsprechende Operationen auch performanter.

Gerade die best- und avarage-case sind durch die zugrunde liegenden Datenstrukturen bestimmt.

Bearbeitet 24. Juni 2010 von flashpixx

[lupo49]

AUFBAU: Suche die Stelle, an der es eingefügt werden soll hat Laufzeitkomplexität O(log n) im worst-case und O(1) im best-case, das einfügen selber O(1) [--> stimmt das?]

|log(n+1)| (Gaussklammer / Aufrunden)

Damit bei n = 1 Knoten der Aufwand nicht zu 0 wird.

INORDERDURCHLAUF: die Laufzeitkomplexität für den best- und worst-case ist O(n), da jeweils alle Elemente durchlaufen werden müssen, um sie sortiert ausgeben zu können [--> stimmt das?]

Wenn du die Elemente unsortiert in einem Baum anordnest, dann hast du ungefähr den gleichen Aufwand wie bei einer Liste, weil dann alle Elemente überprüft werden müssen.

Normalerweise hat man Bäume bei denen in der Wurzel ein Wert steht, dann im linken unteren Knoten ein kleinerer Wert und im rechten unteren Knoten ein größeren Wert. Das gilt dann für jeden weiteren Unterknoten.