Zwei Programme, die dasselbe Ergebnis liefern, können sich dramatisch in ihrer Geschwindigkeit unterscheiden. Wenn du Millionen von Datenpunkten verarbeitest, kann ein ineffizienter Algorithmus Stunden dauern, während ein effizienter in Sekunden fertig ist. Die Zeitkomplexität gibt uns eine Möglichkeit, die Effizienz von Algorithmen zu vergleichen.
Was ist Zeitkomplexität?
Zeitkomplexität misst nicht die absolute Laufzeit (die hängt von der Hardware ab), sondern wie viel langsamer ein Algorithmus wird, wenn die Eingabegröße n wächst.
Die Big-O-Notation
Die Big-O-Notation (gesprochen: "big Oh") beschreibt die Wachstumsrate im schlechtesten Fall. Sie konzentriert sich auf den dominanten Term und ignoriert Konstanten.
Häufige Komplexitätsklassen
O(1) — Konstante Zeit
Der Algorithmus braucht immer gleich lang, egal wie groß n ist:
def erstes_element(liste):
return liste[0] # immer ein einziger Schritt
O(1) ist die effizienteste mögliche Komplexität. Egal ob die Liste 10 oder 10 Millionen Elemente hat — die Operation dauert immer gleich lang.
O(n) — Lineare Zeit
Die Laufzeit wächst proportional zu n:
def summe(liste):
gesamt = 0
for zahl in liste: # n Schritte
gesamt += zahl
return gesamt
Doppelt so viele Elemente → doppelt so lange Laufzeit.
O(n²) — Quadratische Zeit
Die Laufzeit wächst quadratisch — typisch für verschachtelte Schleifen:
def alle_paare(liste):
for i in liste: # n Schritte
for j in liste: # n Schritte für jedes i
print(i, j) # n * n = n² Schritte insgesamt
Bei 10 Elementen: 100 Operationen. Bei 100 Elementen: 10.000 Operationen.
O(log n) — Logarithmische Zeit
Die Laufzeit wächst sehr langsam — typisch für Algorithmen, die das Problem bei jedem Schritt halbieren:
# Binäre Suche: O(log n)
def binaere_suche(liste, ziel):
links, rechts = 0, len(liste) - 1
while links <= rechts:
mitte = (links + rechts) // 2
if liste[mitte] == ziel:
return mitte
elif liste[mitte] < ziel:
links = mitte + 1
else:
rechts = mitte - 1
return -1
log₂(1.000.000) ≈ 20. Das bedeutet: Die binäre Suche findet ein Element in einer Liste mit einer Million Einträgen in maximal 20 Schritten!
Komplexitäten im Vergleich
Für n = 1.000 Elemente:
| Komplexität | Name | Operationen (n=1.000) |
|---|---|---|
| O(1) | Konstant | 1 |
| O(log n) | Logarithmisch | ~10 |
| O(n) | Linear | 1.000 |
| O(n log n) | Log-linear | ~10.000 |
| O(n²) | Quadratisch | 1.000.000 |
| O(2ⁿ) | Exponentiell | 10³⁰⁰ (astronomisch!) |
Bekannte Algorithmen und ihre Komplexität
| Algorithmus | Zeitkomplexität | Anmerkung |
|---|---|---|
| Lineare Suche | O(n) | Muss jedes Element prüfen |
| Binäre Suche | O(log n) | Setzt sortierte Liste voraus |
| Bubble-Sort | O(n²) | Für große Listen zu langsam |
| Einfügesortierung | O(n²) | Gut für fast sortierte Daten |
| Mergesort/Quicksort | O(n log n) | Professionelle Sortierung |
Wenn ein Schüler zwei verschachtelte Schleifen über n Elemente schreibt, ohne es zu merken, hat er möglicherweise einen O(n²)-Algorithmus erstellt. Für kleine Tests mag das funktionieren, aber bei großen Datenmengen kann das Programm extrem langsam werden.
Praktisches Denken über Effizienz
Wenn du zwei Algorithmen entwirfst, die dasselbe Problem lösen, frag dich:
- Wie viele Schritte macht Algorithmus A für
n = 10? Fürn = 100? Fürn = 1000? - Wächst die Schrittzahl linear, quadratisch oder logarithmisch?
# Unterschied zwischen O(n) und O(n²) praktisch sehen
import time
def linear(n):
summe = 0
for i in range(n):
summe += i
return summe
def quadratisch(n):
zaehler = 0
for i in range(n):
for j in range(n):
zaehler += 1
return zaehler
Übungsaufgaben
Ein Algorithmus macht für eine Liste mit 10 Elementen 100 Vergleiche. Für 20 Elemente macht er 400 Vergleiche. Welche Zeitkomplexität hat dieser Algorithmus wahrscheinlich?
Antwort anzeigen
Warum ist O(log n) so viel effizienter als O(n) für große Eingaben? Zeige das mit Zahlen für n = 1.000.000.