Tutorium für Algorithmen und Datenstrukturen

Aufgabe 6-2

(Übungsblatt 6)

Finden Sie einen „halb-naïven“ Lösungsalgorithmus, der ebenfalls im Brute-Force–Verfahren arbeitet, jedoch durch Einsparen einer Schleife eine Zeitkomplexität von O(n²) statt O(n³) erreicht.

1. Nennen Sie den entscheidenden Unterschied zum naïven Algorithmus aus Aufgabe 6-1.
2. Implementieren Sie diesen Algorithmus in sog. „natürlicher Sprache“ entsprechend den Vorlesungsunterlagen der vergangenen Semester.
3. Implementieren Sie diesen Algorithmus in Java.

Lösungsvorschlag

zu den Teilaufgaben:

1. Statt für jedes der ca. n² Teilfelder jeweils eine eigene Schleife mit O(n) laufen zu lassen, um dessen Summe zu ermitteln, kann man in einer der beiden ohnehin vorhandenen Zählschleifen für die Indizes (lower und upper) die Summe direkt mitzählen. Die innerste Schleife (k-Schleife) wird dadurch überflüssig.

2. Parameter: Array A, Arraylänge n
   Rückgabewert: Wert der maximalen Teilsumme

   Maximum–Sub-Array Start
   MTS = -∞ für alle i von 1 bis n

   TS = 0 für alle j von i bis n

   TS = TS + A_j MTS = max(MTS, TS)

   gib MTS als Ergebnis zurück
   Stop

3. Siehe Quellcode: Loesung62c.java