Algorithmus A4

Eine weitere Möglichkeit das Problem zu lösen besteht in der Nutzung eines Divide&Conquer Algorithmus.
Prinzip: Da wir das Problem nicht auf einmal lösen können, zerlegen wir unseren Array in 2 gleich große Teile. Nun gibt es 3 Möglichkeiten:

• Die gesuchte Summe liegt im linken Teil des Arrays ( blau )

• Die gesuchte Summe liegt im rechten Teil des Arrays ( grün )

• Die gesuchte Summe liegt in beiden Teilarrays und wurde im Divide-Schritt geteilt

Im Divide-Schritt wird dieser Array zerlegt in:

Dieses Unterteilen des Arrays kann nun für die Teilarrays weiter fortgeführt werden, bis die Möglichkeit besteht das Teilproblem zu lösen. Dann muß auf geeignete Weise versucht werden, die Ergebnisse geschickt wieder zu einem Ganzen zu kombinieren. Alles in allem führen diese Überlegungen zu folgendem Algorithmus:

Eingabe: Array rationaler Zahlen x der Länge n

Erläuterung:

lmax	maximale Summe im linken Teilarray ( blau ). Gesucht wird hierbei der Index i, für den die Summe sum x[i..n/2-1] maximal wird. Der Wert dieser Summe ist lmax
lmax	Wie lmax nur im rechten Teilarray ( grün ). Hier wird sum x[n/2..i] bestimmt.
m	ist der mittlere Wert zwischen l und u also linker und rechter Grenze

Die beiden if-Schleifen oben im Algorithmus dienen dem Rekursionsabbruch. Aufgehört werden kann genau dann, wenn die linke Grenze >= der rechten ist, denn dann ist die Lösung klar bestimmbar, da nur noch höchstens ein Element im Teilarray vorhanden ist.
Die folgenden beiden Abschnitte zur Bestimmung von lmax bzw. rmax funktionieren auf folgende Weise: ( am Bsp von lmax )
Die maximale Summe ist nach der Einleitung immer >= 0. Daher wird lmax bereits am Anfang auf 0 gesetzt, damit dies gewährleistet werden kann. Wie oben in der Erläuterung beschrieben, wird dann durch sukzessives Aufsummieren der x[j] die Teilsumme sum x[i..n/2-1] bestimmt, wobei die Tatsache von A2 genutzt wird, daß nämlich

sum x[i..n/2-1] = sum x[i+1..n/2-1] + x[i]

ist. Mit Hilfe der max Funktion ist am Ende der Schleife max sum x[i..n/2-1] bestimmt.
Wenn dann anschließend auf ähnliche Weise rmax bestimmt wird, kommt man zur eigentlichen Auswertung.
Hier gilt nun, daß der gesuchte Wert gerade die Summation des linken und rechten Maximums ist ( rot, eben genau dann, wenn das Maximum im Divide Schritt geteilt wurde ) oder, wenn die maximale Summe doch komplett in einem der geteilten Arrays liegt, durch einen weiteren Programmaufruf für die halbierten Arrays ermittelt werden kann ( blau bzw. grün ).

Laufzeit:
Die Laufzeit dieses Divide&Conquer Algorithmus kann als Funktion in n aufgefasst werden.

Anschaulich bedeutet dies:

Nach dem ersten Divide Schritt, wird der Array in 2 Teilarrays zerteilt:

Nach dem zweiten Divide Schritt, wird jeder Teilarray wiederum in 2 zerteilt:

...

Betrachten wir nun, wie oft ein Element für das Ergebnis benutzt wird, so kommen wir zu folgendem Ergebnis:

Wie man schnell sieht, wird in jedem Schritt jedes Element genau 1 Mal benutzt. Die Länge des Arrays ist n, wir haben also n Elemente. Bleibt die Tiefe des Baumes zu bestimmen, damit gezeigt werden kann, wie oft n Elemente benutzt werden.
In jedem Schritt teilen sich in die Arrays in 2 Teilarrays gleicher Größe auf. Das Verfahren stoppt, sobald n<=1 errreicht ist. Somit ist die Frage, wann 0 < (0,5)^i * n <= 1 gilt, zu beantworten. Dies gilt aber gerade für i = log( n ), da
2^log( n ) = n , also da 2^-1 = 0,5
(0,5)^log ( n ) = 1/n , somit also

(0,5)^log( n ) * n = 1

Somit ist die Laufzeit des Verfahrens O( n * log( n ) )

Im Test ergab sich das folgenden Ergebnis:
Für 10.000 Werte benötigte A2 eine Zeit von: 0 sec 10 msec
Für 100.000 Werte benötigte A2 eine Zeit von: 0 sec 90 msec