Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Miniklausur WS 14 Aufgabe 4. a
eine Frage: ich werde aus der Loesung der FSI seite nicht schlau. da ist eine formel fuer die minimale hoehe angegeben. gibt es die noch irgendwo? und steht die irgendwo in den Folien, kann mich beileibe nicht errinnern da mal was davon gesehen zu haben.
Puhh, glaube nicht das die irgendwo steht.
(log(9*n+1)/log(10))-1 ist für n = 11 → 2, ab dem 12 Element ist es dann 2,xx aufgerundet also 3; für n=111 → 3; ab dem 112 Element aufgerundet 4. Wie man darauf kommt, gute Frage.
edit: ahh p=anzahl kinder;
(log((p-1)*n+1)/log(p)) -1
Die Herleitung der Formel erfolgt mittels geometrischer Reihe. Allerdings war diese Formel meines Erachtens auch nicht verlangt. Vielmehr sollte man den Aufwand in O-Notation angeben und somit alle Konstanten für den Fall p=10 kürzen.
Etwas ausführlicher:
Die maximale Anzahl Elemente in einem Baum mit der Höhe 0 ist 1. Bei Höhe 1 ist das 1+p, bei Höhe 2 ist es 1+p+p^2 usw… Setzen wir nun die Formel der geometrischen Reihe ein, ist für Höhe h die maximale Anzahl Elemente gerade (p^(h+1)-1)/(p-1). Nun sei die Anzahl Elemente in einem Baum durch n gegeben. Wir wollen nun h minimieren, sodass n <= (p^(h+1)-1)/(p-1) gilt.
=> n*(p-1) <= p^(h+1)-1 (wegen p-1>0)
=> n*(p-1)+1 <= p^(h+1)
=> log_p(n*(p-1)+1) <= h+1 (wegen der Monotonie des Logarithmus)
=> h >= log_p(n*(p-1)+1)-1 = log(n*(p-1)+1) / log(p) - 1.
Das minimale ganzzahlige h, das diese Bedingung erfüllt, ist ceil(log(n*(p-1)+1) / log(p) - 1).
hmm also wenn das nirgendwo steht, warum dann so eine frage in der Klausur? und geometrische Reihe, habe ich in meinem Leben noch nicht gemacht. Warum wird den sowas in der Klausur abgefragt, wenns nicht mal behandelt wurde?
Ich hab mir auch diese Lösung vor ein paar Tagen angeschaut und hatte nur ein riesiges Fragezeichen vor den Augen hängen.
Nach bissl rumgooglen hab ich mir dann notiert, dass man die minimale Höhe eine Baumes folgendermaßen angeben könnte:
log zur Basis[maximale Anzahl möglicher Kindern] (n)
—> also bei Binärbäumen(max Anzahl Kinder=2): log2(n)
—> bei dem Baum in dieser Aufgabe dementsprechend: log10(n)
stimmt das so und reicht es als Antwort falls so ne Frage in der Klausur drankommt, oder ist das völliger Quatsch?
Ist absolut richtig und genau das was ich auch grade schreiben wollte - danke dass du mir das Tippen erspart hast;)
Für Binärbäume ist die Formel in den VL-Folien, es war als nur ein bisschen Nachdenken verlangt.
1 Like
Die Lösung ist fast richtig. Man muss jedoch noch die Basis kürzen und erhält dann in beiden Fällen einen Aufwand von O(log(n)). Für die maximale Höhe ergibt sich analog O(n).
@NatuerlichesMiner, ja das schaut richtig aus, glaube das auch noch irgendwo in dem zusammenhang gesehen zu haben.
Okay super! Und ist auch auf jeden Fall leichter zu merken, als diese lange Formel in der “Musterlösung” 