Laufzeit von Algorithmen
Um 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 dem zeitlichen Aufwand zur Lösung eines Problems (Zeitkomplexität) und nähern uns damit der Frage nach 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.
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:
| Klasse | Sprechweise |
|---|---|
| \(O(1)\) | konstant |
| \(O(n)\) | linear |
| \(O(n^2)\) | quadratisch |
| \(O(n^k)\) | polynomiell |
| \(O(k^n)\) | exponentiell |