 Thema: Array-Operationen (put, sum) mit garantierter Laufzeit von O(logn n) |
|
|
Hallo Tobias,
ich hab nun Deinen Lösungsvorschlag verstanden und bereits implementiert. Ich weiß nicht, wieso ich so Probleme damit hatte, das zu verstehen, ist vom Prinzip her ja eigentlich echt einfach und von der Implementierung her sehr kurz.
Ich Dank Dir auf jeden Fall noch mal vielmals...
Grüße
|
|
| Thema: Array-Operationen (put, sum) mit garantierter Laufzeit von O(logn n) |
|
|
Ja, vergiss erst mal das mit dem put....
Also die Maximal-Anzahl ist vorgegeben, daher wird nix verschoben.
Meine Frage ist eher, wie kann ich die sum Operation realisieren?
Also wenn ich z.B. aus obigem Beispiel die 4,3,2 addieren will ( sum(2,4) in meinem Beispiel beginnen die Arrays mit 1) so müsst ich in der sum Funktion ja immer überprüfen, ob die Summe bereits ausgerechnet wurde ( 3,2 wurde ja bereits berechnet mit 5) aber die 4 ist ja Teil der Berechnung von 8+4.
Das heißt ich müsste rechnen 4 + (Sum-Pos von (3+2) also 5).
Machen die if-Abfragen das Ganze nicht langsamer, als wenn ich einfach alles aufsummiere?
Irgend eine Idee, wie ich das sum() so umsetzen kann, dass der Binärbaum auch was bringt?
Grüße
|
|
| Thema: Array-Operationen (put, sum) mit garantierter Laufzeit von O(logn n) |
|
|
Hallo erstmal!
Ist mein erster Post hier und ich starte direkt mal mit einer Frage :-)
Vielleicht hat ja jemand eine Idee...
Ich sitz schon seit Tagen an dieser Übungsaufgabe und würde sie gerne lösen...
Gefragt ist folgendes:
Ich habe zwei Funktionen
void put(int pos, int value) // fügt dem Array an der Position pos den Wert value hinzu
int sum(int from_pos, int to_pos) // gibt die Teil-Summe des Arrays von der from_pos bis zur to_pos zurück
Das ist kein Problem.
Jedoch gibt es eine Zusatzforderung:
Beide Operationen sollen eine Laufzeit von jeweils O(log n) besitzen.
Dazu ist es erlaubt O(n) zusätzlichen Speicherplatz zu verwenden, welcher in einen vollständigen binären Baum investiert werden soll (der Baum wird der einfachheit halber in einem Array gespeichert).
Zu dem Binärbaum hab ich mir folgendes überlegt, jedoch kann ich keine Lösung finden, wie ich die zwei Funktionen auf den Baum übertrage...
Der Binärbaum enthält Teilsummen des ursprünglichen Arrays...
Hier mal eine Grafik:
Hier mal noch die verschiedenen Darstellungsmöglichkeiten, welche ich gefunden habe
Ich hoffe, die Grafiken sind einigermaßen übersichtlich!
Bei Fragen, bitte einfach noch mal nachfragen!
Grüße
|
|
|
