Kapitel 4: Komplexitätsanalyse

Die Komplexitätsanalyse erlaubt es, verschiedene Algorythmen in Bezug auf deren Laufzeit (Zeitkomplexität, engl: time complexity) und Speicherbedarf (Speicherkomplexität, engl: sprace complexity) für ein gegebenes Problem zu vergleichen

Häufig steht die Analyse der Zeitkomplexität im Vordergrund, wenn ein Algorythmus den Speicher überfüllt, wird allerdings ebenfalls keine Lösung erzeugt

Die Rate, mit der die Laufzeit eines Algorythmus in Abhängigkeit von der Eingabegröße zunimmt, wird als Wachstumsrate bezeichnet

Als Best-Case Szenario kann die Eingabe verstanden werden, die mit der geringsten Laufzeit gelöst wird

Als Worst-Case Szenarion kann die Eingabe verstanden werden, die mit der maximalen Laufzeit gelöst wird

Als Average-Case Szenarion kann die Eingabe verstanden werden, die mit einer durchschnittlichen Laufzeit gelöst wird

Es handelt sich bei diesem Code um einen Suchalgorythmus, in dem Best-Case und Worst-Case dargestellt werden.

Im besten Fall befindet sich der gesuchte Wert gleich am Anfang der Liste, sodass die for-Schleife nur einmal durchlaufen werden muss. Im schlechtesten Fall ist der gesuchte WErte gar nicht in der Liste enthalten, sodass die for-Schleife n-mal durchlaufen werden muss, wobei n die Länge der Liste ist

Die Big-O Notation bezeichnet die enge obere Schranke g(n) einer gegebenen Funktion f(n). Sie wird dargestellt als f(n) = 0 (g(n))

Das bedeutet, dass bei größeren Werten vo n die Funktion g(n) eine obere Grenze von f(n) ist