Algorithmus A2

Die Zeit, die Algorithmus A1 benötigt, ist für wirklich große Probleme indiskutabel schlecht. Deshalb versucht man nun die Laufzeit von A1 zu verbessern. Dabei hilft einem die folgende Tatsache:

sum x[i..j] = sum x[i..j-1] + x[j]

Dies bedeutet, daß ich die Summe für i und j aus den davor bereits berechneten Werten von i und j-1 durch einfache Addition von x[j] bestimmen kann.

Wenn man diese Überlegung in einen neuen Algorithmus A2 einbaut, so kommt man zu folgenden Ergebnis.

Eingabe: Array rationaler Zahlen x der Länge n

Erläuterung:
Weder die Anzahl noch die Benennung der Variablen hat sich im Vergleich zum Algorithmus A1 geändert, somit ist auch ihre eigentliche Bedeutung identisch geblieben. Lediglich die Art und Weise, wie die Summen der Teilarrays bestimmt werden, ist anders.
Anders als in der innersten ( roten ) Schleife von Algorithmus A1 werden hier die Summen der Teilarrays unter Ausnutzung der Tatsache von oben direkt in der j-Schleife vorgenommen, was die Einsparung der 3. und innersten for-Schleife zur Folge hat. ( Die rote Schleife wurde durch den roten Ausdruck ersetzt )

Laufzeit:
Auch hier kann man schnell erkennen, daß durch die Konstruktion mit 2 for-Schleifen, von denen jede maximal von 0 bis n-1 läuft, eine Laufzeit von O( n² ) errreicht wird.

Im Test ergab sich das folgenden Ergebnis:
Für 10.000 Werte benötigte A2 eine Zeit von: 1 sec 522 msec