×
Kurz-Tutorial: Sechs Klassen
Jede Klasse beschreibt, wie schnell ein Algorithmus bei wachsender Eingabe langsamer wird.
O(1) Konstant
Egal wie groß die Eingabe ist, der Aufwand bleibt gleich. Analogie: ein Lichtschalter braucht immer einen Klick.
def erstes(liste):
return liste[0]
O(log n) Logarithmisch
Halbiert in jedem Schritt das Problem. Analogie: Wort im Telefonbuch suchen, indem du es immer in der Mitte aufschlägst.
while links <= rechts:
mitte = (links + rechts) // 2
...
O(n) Linear
Jedes Element wird einmal angeschaut. Analogie: Klassenliste durchgehen und einen Namen finden.
for x in liste:
if x == ziel:
return True
O(n log n) Effizientes Sortieren
Die schnellste Klasse für vergleichsbasiertes Sortieren. Analogie: Merge Sort teilt die Liste rekursiv und fügt sie sortiert zusammen.
merge_sort(links) + merge_sort(rechts)
# plus lineares Zusammenfügen
O(n^2) Quadratisch
Zwei verschachtelte Schleifen über die Eingabe. Analogie: in einer Runde gibt jeder jedem die Hand.
for i in range(n):
for j in range(n):
...
O(2^n) Exponentiell
Verdoppelt sich mit jedem zusätzlichen Element. Analogie: bei jedem neuen Schalter verdoppelt sich die Zahl möglicher Schalter-Stellungen.
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
