Laufzeiten von Algorithmen

Bisweilen können für die selbe Aufgabe mehrere Lösungen gefunden werden, die sich teilweise jedoch erheblich in ihrer Effizienz unterscheiden. Bei der Effizienz-Analyse eines Algorithmus, also eines “Rezepts” zur Lösung eines Problems, ist es insbesondere von Interesse, wie sich die Laufzeit in Abhängigkeit von der Anzahl n der zu bearbeitenden Daten ändert.

Zur Analyse von Laufzeiten sind prinzipiell zweierlei Vorgehensweisen möglich:

  • Mittels eines Benchmarks wird ein Programm oder Algorithmus mit einem möglichst typischen Satz an Daten aufgerufen und dabei die benötigte Zeit gemessen.

    Ein Werkzeug, das hierfür unter Linux genutzt werden kann, ist gprof. Dieses Programm misst nicht nur die Laufzeit eines Programms und der im Programmverlauf aufgerufenen Funktionen, sondern zählt auch, wie häufig die einzelnen Funktionen aufgerufen wurden. Damit erhält man einen guten Überblick, welche Funktionen für eine weitergehende Analyse “wichtig” sind.

  • Mit einer Laufzeit-Analyse kann anhand der Struktur des Quellcodes, beispielsweise anhand der Anzahl an Schleifendurchläufen, Lese- oder Schreibvorgängen, die Größenordnung der Laufzeit eines Algorithmus in Abhängigkeit von der Anzahl n an zu bearbeiteten Daten abgeschätzt werden.

Die “Big-O”-Notation

Wie lange die Ausführung eines Algorithmus tatsächlich benötigt, hängt nicht zuletzt von der Rechenleistung des Computers ab, auf dem der Code ausgeführt wird; Benchmarks müssen daher auf einem einheitlichen System durchgeführt und unter Angabe der Rechnerleistung (CPU, RAM, usw.) angegeben werden. Allgemeinere Vergleiche sind hingegen möglich, welche die Laufzeit t eines Algorithmus allgemein als Funktion t(n) des Datenumfangs n ausgedrückt wird. Wird beispielsweise im Verlauf eines Programms eine Funktion mit einer konstanten Laufzeit c insgesamt n mal aufgerufen, so ergibt sich dadurch eine Laufzeit von t(n) = c \cdot n.

Beim Zählen von Laufzeiten wird üblicherweise die vereinfachende Vereinbarung, dass die folgenden Prozess-Schritte zur Ausführung jeweils eine Zeiteinheit benötigen:

  • Jede Wertzuweisung
  • Jeder Wertevergleich
  • Jede Iteration einer Schleifenvariablen

Finden beispielsweise beim Durchlaufen einer Schleife n Iterationen statt, so nimmt die Laufzeit für einen Aufruf einer solchen Schleife linear mit n zu. Man sagt, dass in diesem Fall die Laufzeit proportional zur Größenordnung von n ist, und schreibt hierfür in Kurzform \mathcal{O} (n). Wird hingegen eine verschachtelte Liste mit n Teillisten durchlaufen, die wiederum n Einträge haben, so sind insgesamt n \cdot n = n^2 Iterationen nötig. Entsprechend ergibt sich für einen Aufruf einer derartigen Schleife eine Laufzeit in der Größenordnung von \mathcal{O}(n^2).