Laufzeit von Algorithmen

Theorie IconUm zu beurteilen, ob ein Algorithmus effizient ist, müssen wir ermitteln mit welchem Aufwand dieser Algorithmus ein Problem löst. Im Folgenden beschäftigen wir uns mit der Frage, den zeitlichen Aufwand zur Lösung des Problems zu ermitteln (Zeitkomplexität) und damit mit der Laufzeit eines Algorithmus.

Laufzeit

Die Laufzeit soll nicht als konkrete Zahl angeben werden, z. B. in Sekunden. Vielmehr erwarten wir hier einen Term, mit dem die Berechnung der Laufzeit in Abhängigkeit von \(n\) angenähert wird. Als Maßeinheit wird die Anzahl der auszuführenden Operationen angegeben.

Die Laufzeit eines Algorithmus mit der Eingabe der Länge \(n\) ist definiert durch die Funktion \(T(n)\).

Komplexitätsmaße

Wir unterscheiden drei verschiedene Maße, mit denen sich Aussagen über den Zeitbedarf eines Algorithmus treffen lassen:

  • Der beste Fall (best case)  \(T_\text{best}\)
    In diesem Fall kann die Lösung am Schnellsten berechnet werden.
  • Der schlechteste Fall (worst case)  \(T_\text{worst}\)
    In diesem Fall dauert die Lösung am Längsten.
  • Der Durchschnittsfall (average case)  \(T_\text{average}\)
    Hier entspricht die Laufzeit der durchschnittlichen Dauer über alle zu erwarteten Eingaben.

Komplexitätsklassen

Die Laufzeiten von Algorithmen werden mithilfe der O-Notation in verschiedene Klassen eingeteilt:

KlasseSprechweise
\(O(1)\)konstant
\(O(n)\)linear
\(O(n^2)\)quadratisch
\(O(n^k)\)polynomiell
\(O(k^n)\)exponentiell

Übung