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

Hallo, vielen lieben Dank für die ganzen ausführlichen Antworten. Habt mir sehr weitergeholfen und denke es jetzt verstanden zu haben :-) Viele Grüße

mhhh OK, das stimmt... also müsste es heißen g(x)=x*n [seq. Suche] f(x)= x*(n*log(n)+log(n)) [binäre Suche] wobei x die Anzahl der Suchanfragen und n die Größe des Arrays ist? Dann komme ich aber immer noch nicht weiter. Sorry habe gerade glaube ich ein Brett vor dem Kopf bei der Aufgabe.. Wohin muss ich das auflösen bzw. wie in Verbindung setzen, um allgemein die Anzahl der Suchanfragen zu erhalten, ab der sich die binäre Suche lohnt?

Hallo, vielen Dank für Eure ausfürhlichen Antworten! habe jetzt folgendes vorgehen gewählt: - die Funktionen f(x)=n [max. Aufwand (sequentielle Suche)] und g(x)=log(n)+n*log(n) [max. Suchaufwand + Sortieraufwand (binäre Suche)] plotten lassen. Den Schnittpunkt bestimmt (liegt bei ca. S(1,5|1,5)). Allerdings steigt die Funktion n*log(n)+log(n) viel schneller an, als n und daher ist das mit der Behauptung binäre Suche sei schneller nicht schlüssig. Danke, Viele Grüße Dan

Hallo, muss bis nächsten Montag folgende Aufgabe lösen: ******************************************* AUFGABENSTELLUNG: gegeben sei ein Feld der Länge n. Ab wie vielen Suchanfragen lohnt sich eine binäre Suche im Vergleich zu einer sequentiellen Suche? (wir gehen vom worst-case aus) Es gilt zu beachten, dass die binäre Suche eine Vorsortierung der Daten voraussetzt. Dies ist durch einen Zeitaufwand von O(n log n) möglich. ******************************************* ÜBERLEGUNGEN: worst-case sequentielle Suche: O(n) = Suchaufwand worst-case binäre Suche: log2(n) = Suchaufwand (= obere Schranke des Logarithmus von n zur Basis 2) binäre Suche: n*log(n) Sortieraufwand der Sortieraufwand lohnt sich also wenn n>log2(n)+n*log(n) Stimmt das? Wenn ja zu welcher zu welcher Basis gehört n*log(n) und wie bekomme ich heraus ab wie vielen Suchanfragen sich das lohnt. Danke im voraus, Viele Grüße Dan

vielen Dank für die schnelle Antwort. Hat geklappt -> Induktion war der entscheidende Tipp

Hallo, wir müssen für unsere nächste Klausur eine Formel beweisen. Ich kann zwar durch ausprobieren erkennen, dass die Formel korrekt ist, aber habe keine Ahnung wie ich das beweisen kann. ******************************** FOLGENDE PROBLEMSTELLUNG: - wie berechnet man die Anzahl aller Knoten eines Baumes, wobei die Baumgröße zum einen von der Tiefe des Baumes, zum anderen davon abhängt, wie viele Kindknoten jedes Kind hat. Es gilt: - die Tiefe aller Blaetter ist gleich - er ist echt dÄr (alle Knoten außer den Blättern haben denselben Grad) FORMEL: (d^(t+1)-1)/d-1 t:= Tiefe des Baumes d:= Grad Setze ich für z.B. d = 3 und t = 2 ein, erhalte ich 13. Dies ist z.B. ja auch die Korrekte Anzahl der Knoten dieses Baumes. Wie kann ich das allgemeiner beweisen oder diese Formel herleiten? Vielen Dank für Eure Mühen, André