Die folgende Übersicht fasst die relevanten Informationen zur Landaunotation für Laufzeiten (auch Zeitkomplexitäten genannt) von Algorithmen zusammen. Mit Laufzeit ist dabei die Anzahl der Operationen, nicht die tatsächliche Zeit gemeint.
- worst case - Anzahl benötigte Operationen im schlechtesten Fall
- best case - s.o., jedoch im besten Fall
- average case - arithmetisches Mittel aller möglichen Laufzeiten
Achtung: Zeitkomplexität T immer in Abhängigkeit der Länge der Eingabe (n) angeben! => T(n)...
Landau-Notation
Zur Abschätzung der Laufzeit.
T(n) ∈ O(n) bedeutet, die Laufzeit wächst in Abhängigkeit von n nicht wesentlich schneller als die Funktion g(n) = n²
Es gibt weitere Landau-Symbole, die wir aber nicht behandeln.
Nach dem Ermitteln einer Laufzeitfunktion erfolgt eine Abschätzung bzw. Einordnung in die Komplexitätsklassen. Dabei fallen alle den Funktionsverlauf nicht wesentlich beeinflussende Elemente weg.
Beispiel: Aus T(n) = 6n² -3n + 999 wird T(n) ∈ O(n²)
Komplexitäts-klasse (ansteigend) | in Worten | ggf. Beispiel |
|---|---|---|
1 | konstant (es gibt eine feste Obergrenze) | ist eine Binärzahl gerade? |
log(n) | logarithmisch | binäre Suche |
n | linear | lineare Suche |
n log(n) |
| Merge-/Heapsort |
n² | quadratisch | Bubble- Insert- Selectionsort |
n^m | polynomiell | |
2^n | exponentiell | |
n! | faktoriell | Traveling Salesman |
Ein Algorithmus gilt dann als effizient, wenn er maximal polynomielle Zeitkomplexität besitzt.
https://www.tutory.de/entdecken/dokument/laufzeit-und-effizienz-von-algorithmen
