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.
Klausur 25.02.2010 - Haldeneigenschaft herstellen
Hallo,
Bei Aufgabe 5 Halde sollte man ja die Haldeneigenschaft herstellen. Laut der Vorlesung geht das ja in O(n) (und nicht naiv O(n log n)). Gibt es dafuer ein Code-Beispiel? Weil ich gerade nicht wuesste ich das implementieren wuerde.
Danke,
Simon
haldeneigenschaft herstellen geht mit O(log n) (Folie 14-43) im fall, das ein element gelöscht wird.
haldeneigenschaft herstellen, wenn die halde quasi von “unten her aufgebaut” wird, dauert O(nlog n)
haldensortierung genauso O(nlog n)
Ich würde die Halde bottom-up aufbauen.
In der Aufgabe dann etwa so (Länge/2, da die Hälfte der Knoten ja Blätter sind und die braucht man nicht zu versickern):
for (int i = feld.length/2 - 1; i >= 0; i--) {
versickern(feld[], i, feld.length -1);
}Nur ganz so sicher bin ich mir da auch nicht :huh:
Sorry, da war ich nicht praezise. Die Aufgabe meinte Haldeneigenschaft auf einem unsortierten Feld herstellen. Also das ganze ist noch keine Halde.
Und in der Vorlesung steht auf Seite 45 dass das in O(n) geht. Zwar geht deshalb Heapsort immer noch nicht schneller, da hast du Recht, aber in der Klausuraufgabe steht “so effizient wie moeglich” und das klingt fuer mich nach O(n).
wobei ich jetzt auch einfach mal der meinung bin, dass man es so macht wie knix geschrieben hat. das wäre zwar O(n logn) - ich wüsst aber nicht, wie man es in O(n) machen soll. das ist auch die in den folien beschriebene vorgehensweise und ich denke (bzw. hoffe), das sollte reichen.
Sieht gut aus. Danke. Laut Vorlesung sollte das auch in O(n) sein (auch wenn ich das nicht wirklich verstehe).
Meiner Meinung nach ist das in O(n) ∙ O(log n) = O(n∙logn):
- man geht die reihung zur hälfte durch: O(n/2)=O(n)
- das versickern dauert maximal O(logn) ⇒ O(n∙logn)
Die Methode mit O(n) ist nicht wirklich beschrieben.
Dachte ich eigentlich auch. Aber auf Folie 50 steht da noch ne Berechnung und die kommt auf O(n). Aber da mir keine andere Methode einfaellt, wuerde ich einfach knixs nehmen und hoffen das es passt.
die ganze klausuraufgabe ist sowieso merkwürdig, hab da insgesamt nur 5 zeilen code 0o
Ja ich auch, die Aufgabe war sehr kurz zu machen … danke nochmal an knix fuer die Loesung.
Man muß ja nur das halbe Array aufbauen (14-47). Siehe Code von knix. Also n/2 mal versickern, wobei der Aufwand des einfügens des i-ten Elementes log(i) ist. Also ist der Gesamtaufwand
Summe i=n/2 bis n über log(i).
[s]Laut einem bekannten Algebraprogramm geht das asymptotisch gegen n… 
An einem korrekten mathematischen Beweis währe ich durchaus interessiert, ich brings grad nicht hin.
Auf jeden Fall ist der Aufwand dann tatsächlich O(n).[/s]
Ahh falsch… was gibt denn die Summe?
Der Code für die eigentliche sortierung (aufgabe 5c) war dann doch:
for(int i = 0; i < feld.length; i++) {
tausche(feld, 0, feld.length-(i+1));
versickern(feld, 0, feld.length-(i+2));
}Oder hab ich was übersehen und es ist doch nicht so einfach?
die eckige klammerung gehört weg, die -1 hmm naja kommt auf die implementierung von versickern drauf an 
kann man jemand uns sagen wie ist die Lösung von der aufgabe a)
danke
siehe auch oben…
Bin der meinung, dass das so stimmen sollte und die lösung der 5a) ist…
Ich hab hier noch ein if (i == field.length - 2) { break; } weil er sonst versickern von 0 bis -1 aufruft.
wenn i = feld.length-2 ist, ruft er auf
versickern(feld, 0, feld.length-(feld.length-2+2));
⇒ versickern(feld, 0, 0);er versickert somit nur das den ersten eintrag, was doch möglich sein sollte. es ändert sich halt nix…
falsch ist das if nicht, ich denke nur, dass es auch ohne geht.
Ja, aber es kommt danach doch noch field.length - 1 (da i < field.length), und dann wird es negativ, oder verrechne ich mich da gerade?