Bei Problemlösungen spielen zwei Faktoren eine wichtige Rolle:

• Wie schnell löst der benutzte Algorithmus das Problem? 
• Wieviel Speicherplatz wird für die Lösung eines problems benötigt? 

Material:   Folien (Vortrag)

Die Zeit, die ein Algorithmus zur Lösung eines problems benötigt, hängtstark von der "Größe des Problems" ab. Eine Liste mit 100 Einträgen kann wesentlich schneller durchsucht werden als eine mit 1 Mio. Einträgen. Letztlich geht es dabei oft um die Frage, wie oft Schleifen wiederholt werden.

Heute schwelgt man im Speicherüberfluss und kaum einer macht sich noch Gedanken über den Speicherumfang, den man für ein Programm benötigt. Dabei gibt es zahlreiche Anwendenungen, denen nicht genügend Speicher zur Verfügung steht und die deshalb die langsame Festplatte als "Swap"-Speicher mitverwenden müssen. Kernstück eines schnellen Algorithmus ist deshalb auch, ob alle benötigten Daten im RAM Platz finden.

Unter der Komplexität eines Algorithmus versteht man den durchschnittlichen Aufwand eines Verfahrens bezögen auf die "Größe des Problems". Dabei spielen folgende Kriterien eine wichtige Rolle:

• Man unterscheidet nicht die Art der Elementaroperationen
  ("alles dauert gleich lang")
• Man unterscheidet "Komplexitätsklasse"
  (z. B. Array beliebigen Inhalts der Größe n)
• Innerhalb der Komplexitätsklassen betrachtet man das Durchschnittsverhalten für alle möglichen Fälle(worst-case, best-case)
• Die Betrachtung soll Hardware-unabhängig sein
• Durch das Weglassen von multiplikativen und additiven Konstanten wird nur noch das Wachstum einer Laufzeitfunktion T(n) betrachtet.

Gewöhnlich wird die Komplexität in der sogenannten O-Notation angegeben. Die Laufzeit T(n) wird dabei durch eine Funktion g(n) abgeschätzt, die als kleinste obere Schranke gewählt wird.

T(n) <= konst * g(n) für alle n>n0

Die Laufzeit hat dann die Komplexität O(g(n)).

Beispiel:

Die Suche eines Elements in einer Reihung besitzt die Komplexität O(n), da die Reihung im schlechtesten Fall ganz durchlaufen werden muss.

• Im besten Fall ist das erste Element das gesuchte (T = 1)
• Im schlechsten Fall muss dasFeld ganz durchlaufen werden (T=n)
• Im Durchschnitt muss man (1+2+..+n)/n Vergleiche durchführen (T=(n+1)/2)

Auf jeden Fall kann die Laufzeit wie folgt abgeschätzt werden:

T(n) <= 1 * n     ( mit g(n) = n )

Also ist die Komplexität O(n).

Beim Sortieren der Reihung mit dem (schlechten) Bubblesort-Algorithmus muss das Feld n² - mal durchlaufen werden. Dieser Algorithmus hat also die Komplexität O(n²). Auch die optimierte Version des Bubblesortalgorithmus besitzt diese Komplexität, da

T(n) = n*(n+1)/2 = n²/2 + n/2 <= 1*n²  ( mit g(n) = n² )

Anmerkung: Für sehr große n spielt der Summand n/2 keine Rolle mehr, das Wachstum wird ausschließlich von n²/2 bestimmt. Da bei der Komplexität Faktoren (1/2) unberücksichtigt bleiben, ist die Komplexität des Bubblesort-Algorithmus O(n²).

Welche Komplexität besitzt die iterative Summenberechnung der ersten n Zahlen?

  public long summe(int n) {
     long sum = 0;
     for (long i = 0; i < n; i++)
        sum += i;
     return sum;
  }

Da die Berechnung der Summe über eine Zählschleife geht, ist die Komplexität O(n): eine Verdopplung von n führt zu einer Verdopplung der Laufzeit. Dieser lineare Anstieg wird durch eine Laufzeitmessung bestätigt.

In Java kann man über die Funktion System.currentTimeMillis() die aktuelle Systemzeit in Millisekunden abfragen. Tut man dies unmittelbar vor und nach dem Aufruf der Methode summe, dann ist die zeitdifferenz ein Maß für die Laufzeit. Die gemessene Zeit hängt zwar von der verwendeten Hardware ab, allerdings zeigt ein schnellerer Rechner prinzipiell ein ähnliches Verhalten (flacherer Anstieg).

Für 3-D-Grafiken müssen häufig Matrizenmultiplikationen durchgeführt werden. Die folgende Methode berechnet das Produkt zweier nxn-Matrizen.

  public void matrixmultiplikation(int n) {
    for (int i = 0; i < n; i++)
       for  (int j = 0; j < n; j++) {
           c[i][j] = 0;
           for (int k = 0; k < n; k++)
              c[i][j] = c[i][j] +a[i][k]*b[k][j];
       }
 }

Die Laufzeitmessung bestätigt die Komplexität O(n³) (die gestrichelte Linie entspricht der Potenzfunktion n³).

Aufgabe:

• Implementiere eine Funktion mymulti, die einen String n-mal verkettet zurückliefert. Verwende hierzu die einfache Stringverkettung durch das "+"-Zeichen.
• Implementiere eine Funktion multi, die dasselbe macht, sich allerdings auf die vordefinierte Funktion concat stützt.
• Vergleiche die Laufzeiten und stelle diese grafisch mit einem Tabellenkalkulationsprogramm dar.
• Welche Komplexität besitzen die beiden Algorithmen?