• Laufzeit und Effizienz von Algorithmen
  • verybusybeaver
  • 02.02.2021
  • Informatik
  • 11, 12, 13
Um die Lizenzinformationen zu sehen, klicken Sie bitte den gewünschten Inhalt an.
  • 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.

    Laufzeiten / betrachtete Fälle
    • 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.

    Abschätzung und Vereinfachung

    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)

    super-linear

    Merge-/Heapsort

    quadratisch

    Bubble- Insert- Selectionsort

    n^m

    polynomiell

    2^n

    exponentiell

    n!

    faktoriell

    Traveling Salesman

    Effiziente Algorithmen

    Ein Algorithmus gilt dann als effizient, wenn er maximal polynomielle Zeitkomplexität besitzt.