Array-Operationen (put, sum) mit garantierter Laufzeit von O(logn n)

03.02.2007, 15:38

hypersound

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

03.02.2007, 16:18

Auf diesen Beitrag antworten »

Tobias

Ich versteh nicht so ganz, wie du so die put-Operation in O(logn) machen willst. Gerade wenn man den Baum in einem Array speichert, muss man doch bei put() evt. das ganze Array verschieben. Wie sieht es z.B. aus, wenn du eine neue Ebene aufmachen musst? Es ist ja gerade nicht immer gewährleistet, dass der Baum vollständig ist.

03.02.2007, 17:43

Auf diesen Beitrag antworten »

hypersound

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

03.02.2007, 18:14

Auf diesen Beitrag antworten »

Tobias

Das würde ich rekursiv machen.

Nach dem Motto divide&conquer. Hier ein Ansatz:

Das Array habe 2^t Elemente.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

 sum(from, to) {
    return sum(1, 2^t, from, to);
 }

 sum(x, y, from, to) {

   if ((from < x) || (to > y))
     return 0;

   if ((x == from) && (y == to))
      return vorberechneter Wert aus dem Baum, der das Intervall [x,y] abdeckt

  else {// Intervall aufteilen
      
      // die ... musst du natürlich noch entsprechend aus from und to berechnen
      return sum(x, y/2, ..., ...) + sum(x/2+1, y, ..., ...);

   }

 }

04.02.2007, 14:00

Auf diesen Beitrag antworten »

hypersound

Hallo Tobias,

erst mal vielen Dank für Deine Mühe.
Ich weiß auch nicht warum, aber bei dieser Aufgabe steh ich irgendwie ziemlich auf dem Schlauch.

Kannst Du vielleicht noch ein bisschen was zu Deinen Lösungsansatz posten?

Wofür ist z.B. das x, y?

Gruß

04.02.2007, 16:26

Auf diesen Beitrag antworten »

Tobias

Also du hast eine Folge $[latex]\big(x_1, \ldots, x_{2^n}\big)[/latex]$ , die dein Array darstellt. Nun willst du eine Summe von a bis b berechnen: $[latex]\sum_{i=a}^b x_i[/latex]$ .

Dabei hast du vorberechnete Summen, die im Binärbaum abgespeichert sind:

$[latex]\sum_{i=1}^{2^n}x_i[/latex]$

$[latex]\sum_{i=1}^{2^{n-1}}x_i \quad , \quad \sum_{i=2^{n-1}+1}^{2^n}x_i [/latex]$

usw.

Du musst nun also dein Intervall a, a+1, ..., b so zerlegen, dass du möglichst große Teilintervalle schon vorberechnet hast. Und das machst du eben rekursiv nach folgender Methode:

Das größe vorberechnete Intervall ist die Summe des ganzen Arrays. Prüfe, ob [a,b] dieses Intervall ist. Wenn nicht, dann sind die beiden nächst kleineren Intervalle gerade zwei Intervalle, die das Array jeweils zur Hälfte aufsummiert haben. Hier musst du also zweimal prüfen, ob eines der Intervalle komplett in [a,b] enthalten ist. Wenn ja kannst du die vorberechnete Summe benutzen und mit dem Restintervall fortfahren. Wenn auch diese beiden Intervalle nicht reichen, dann splittest du weiter auf, usw.

05.02.2007, 05:43

Auf diesen Beitrag antworten »

hypersound

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

Neue Frage »

Antworten »

Array-Operationen (put, sum) mit garantierter Laufzeit von O(logn n)

Verwandte Themen