Algorithmen Anfänger 30 min

Big-O Notation

Big-O ist das Standard-Werkzeug, um Algorithmen zu vergleichen. Lerne O(1), O(log n), O(n), O(n log n), O(n²) - und wie du sie erkennst.

Aktualisiert:
Inhaltsverzeichnis

Big-O Notation

Big-O ist eine Notation fuer die Wachstumsrate eines Algorithmus. Sie sagt dir: Wenn die Eingabe 10x groesser wird, wie viel langsamer wird das Programm?

Versteh das - und du siehst sofort, welcher Algorithmus fuer welches Problem taugt.

Die Grundidee

Stell dir zwei Algorithmen vor, die eine Liste von N Elementen verarbeiten:

  • A: Schaut jedes Element einmal an → Zeit waechst linear mit N
  • B: Vergleicht jedes Element mit jedem anderen → Zeit waechst quadratisch mit N

Bei 10 Elementen: A = 10 Schritte, B = 100 Schritte - kein Problem.

Bei 1.000.000 Elementen: A = 1 Million Schritte, B = 1 Billion Schritte - A laeuft in Millisekunden, B in Stunden.

Die Konstanten sind egal - was zaehlt, ist die Wachstumsrate.

Die wichtigsten Klassen

O(1) - konstant

Unabhaengig von der Groesse der Eingabe - immer gleich schnell.

def erstes_element(liste):
    return liste[0]    # ein Schritt, egal wie gross die Liste

Beispiele: Array-Zugriff via Index, Hash-Table-Lookup (Average).

O(log n) - logarithmisch

Bei jeder Verdoppelung der Eingabe kommt ein Schritt dazu. Sehr schnell.

def binaere_suche(sortierte_liste, ziel):
    links, rechts = 0, len(sortierte_liste) - 1
    while links <= rechts:
        mitte = (links + rechts) // 2
        if sortierte_liste[mitte] == ziel:
            return mitte
        if sortierte_liste[mitte] < ziel:
            links = mitte + 1
        else:
            rechts = mitte - 1
    return -1

Bei 1 Million Elementen: ~20 Schritte. Wow.

O(n) - linear

Zeit waechst proportional zur Eingabegroesse.

def summe(zahlen):
    total = 0
    for z in zahlen:
        total += z
    return total

Bei 1 Million: 1 Million Schritte - immer noch OK in Millisekunden.

O(n log n) - “loglinear”

Die Untergrenze fuer allgemeine Sortieralgorithmen.

sorted_liste = sorted(liste)   # Python's Timsort

Bei 1 Million: ~20 Millionen Schritte - noch schnell (Sekunden).

O(n²) - quadratisch

Geschachtelte Schleifen ueber die gleiche Liste - langsam bei grossen Eingaben.

def duplikate_finden(liste):
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return True
    return False

Bei 1 Million: 1 Billion Schritte - Stunden.

O(2ⁿ) - exponentiell

Katastrophal bei allem ausser sehr kleinen Eingaben.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)    # zwei rekursive Aufrufe

Bei n = 50: ca. 1 Billiarde Schritte. Unbrauchbar.

O(n!) - faktoriell

Alle Permutationen durchprobieren. Nur fuer sehr kleine N.

def alle_permutationen(liste):
    # Wird in Kuerze explodieren
    ...

Vergleich konkret

Bei einer Eingabe der Groesse 100.000:

Klasse~SchritteDauer bei 10⁹ ops/sec
O(1)1< 1 μs
O(log n)~17< 1 μs
O(n)100.0000.1 ms
O(n log n)~1.700.0001.7 ms
O(n²)10 Milliarden10 Sekunden
O(2ⁿ)astronomisch grossUniversum-Lebensdauer

Du siehst: Zwischen O(n log n) und O(n²) liegen Welten.

Regeln zum Berechnen

1. Konstanten fallen weg

O(5n) → O(n). O(3n + 5) → O(n).

Nur die Wachstumsrate zaehlt, nicht absolute Zahlen.

2. Niedrigere Ordnungen fallen weg

O(n² + n) → O(n²). O(n log n + n) → O(n log n).

Bei grossen n dominiert der hoechste Term.

3. Geschachtelte Schleifen multiplizieren sich

for i in range(n):        # O(n)
    for j in range(n):    # O(n)
        ...               # O(1)
# Gesamt: O(n * n) = O(n²)

4. Sequenzielle Operationen addieren

def beispiel(liste):
    # Erste Schleife: O(n)
    for x in liste:
        print(x)
    # Zweite Schleife: O(n)
    for x in liste:
        print(x)
# Gesamt: O(n + n) = O(2n) = O(n)

5. Nur das Maximum zaehlt

def beispiel(liste):
    for x in liste:               # O(n)
        pass
    for i in liste:               # O(n²)
        for j in liste:
            pass
# Gesamt: O(n) + O(n²) = O(n²)

Best, Worst, Average

Manchmal haengt die Laufzeit von der Eingabe ab:

Quicksort

  • Best: O(n log n) - gut gewaehlter Pivot
  • Average: O(n log n)
  • Worst: O(n²) - schlechtester Fall (bereits sortierte Liste mit naivem Pivot)

In der Praxis nennt man meist den durchschnittlichen Fall.

Platzkomplexitaet

Gleiche Notation - aber fuer Speicher statt Zeit:

def duplikate_mit_set(liste):
    return list(set(liste))  # O(n) Platz - neues Set

Vs.:

def summieren(liste):
    total = 0
    for z in liste:
        total += z
    return total      # O(1) Platz - nur `total` wird gespeichert

Beide haben O(n) Zeit, aber unterschiedlichen Speicher-Verbrauch.

Haeufige Fallen

in auf einer Liste ist O(n)

if wert in liste:       # O(n)

in auf einem Set ist O(1)

bekannt = set(liste)     # einmalig O(n)
if wert in bekannt:      # O(1)

Das ist ein haeufiges Pattern zur Optimierung.

String-Konkatenation in Schleife ist O(n²)

# Schlecht - jede Konkatenation kopiert den ganzen String
ergebnis = ""
for wort in woerter:
    ergebnis += wort

Besser:

# O(n) - Python optimiert das
ergebnis = "".join(woerter)

Amortisierte Komplexitaet

Manchmal ist eine Operation im Schnitt schnell, auch wenn einzelne langsam sind.

Beispiel: Python-Liste append:

  • Meistens O(1) - einfach am Ende einfuegen
  • Manchmal O(n) - wenn das zugrunde liegende Array neu allokiert werden muss

Amortisiert: O(1) - ueber viele Operationen gemittelt.

Praktisches Beispiel - Analyse

def dupe_finder(liste):
    gefunden = {}
    for i, x in enumerate(liste):
        if x in gefunden:
            return (gefunden[x], i)
        gefunden[x] = i
    return None

Analyse:

  • Zeit: O(n) - jedes Element einmal, Dict-Lookup ist O(1)
  • Platz: O(n) - Worst Case: alle Elemente unique im Dict

Vergleich zur naiven Loesung:

def dupe_finder_naiv(liste):
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return (i, j)
    return None
  • Zeit: O(n²)
  • Platz: O(1)

Bei kleinen Listen ist die naive Version OK - bei grossen der Dict-Ansatz massiv besser.

Wann ist Big-O egal?

Bei kleinen Eingaben. Fuer 10 Elemente ist O(n²) kein Problem. Der Mehraufwand, einen schnelleren Algorithmus zu schreiben, lohnt sich erst, wenn die Daten gross werden.

Die Frage ist: Wie gross koennte die Eingabe werden?

Zusammenfassung

  • Big-O misst Wachstumsrate, nicht absolute Zeit
  • Wichtige Klassen: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
  • Konstanten und niedrigere Ordnungen fallen weg
  • Geschachtelte Loops multiplizieren sich
  • Space Complexity ist wichtig, nicht nur Time
  • in auf Liste = O(n), auf Set/Dict = O(1) - haeufiges Optimierungs-Pattern

Im naechsten Kapitel: Datenstrukturen - Arrays, Listen, Hash-Tables.

Zurück zum Algorithmen Kurs