algorithmen

Algorithms (Algorithmen)

Kurz: Eine eindeutige, schrittweise Anleitung zur Lösung eines Problems — unabhängig von einer konkreten Programmiersprache, aber die Grundlage für jeden tatsächlichen Programmcode.

Genauer: Algorithmen werden meist nach ihrer Effizienz verglichen (wie stark wächst die benötigte Zeit/der Speicher mit der Eingabegröße) — bekannte Beispiele sind Sortier- und Suchalgorithmen. Die Wahl der passenden Datenstruktur hat oft mindestens so großen Einfluss auf die Performance wie der Algorithmus selbst.

Im Detail

Damit etwas als Algorithmus zählt, muss es drei Eigenschaften erfüllen: er muss eindeutig definiert sein (jeder Schritt ist klar, keine Interpretationsspielräume), endlich sein (er terminiert irgendwann, siehe die Abbruchbedingung bei Rekursion) und effektiv sein (jeder Schritt ist tatsächlich ausführbar).

Die Effizienz eines Algorithmus wird üblicherweise mit der “Landau-Notation” (Big-O) beschrieben, die angibt, wie die Laufzeit mit wachsender Eingabegröße n skaliert:

O(1)       - konstant: Zugriff auf ein Array-Element per Index
O(log n)   - logarithmisch: binäre Suche in einer sortierten Liste
O(n)       - linear: einmal durch eine Liste iterieren
O(n log n) - z. B. effiziente Sortierverfahren (Merge Sort, Quick Sort)
O(n²)      - quadratisch: verschachtelte Schleife über dieselbe Liste (Bubble Sort)

Ein klassisches Beispiel, das den Unterschied zwischen zwei Algorithmen für dasselbe Problem zeigt — die Suche nach einem Wert:

# Lineare Suche: O(n), funktioniert auf unsortierten Daten
def lineare_suche(liste, ziel):
    for i, wert in enumerate(liste):
        if wert == ziel:
            return i
    return -1
 
# Binäre Suche: O(log n), braucht aber eine SORTIERTE Liste
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

Bei kleinen Eingaben (wenige Elemente) macht der Unterschied zwischen O(n) und O(log n) praktisch kaum etwas aus — bei Millionen von Einträgen ist er der Unterschied zwischen Millisekunden und spürbaren Wartezeiten. Deshalb lohnt sich algorithmisches Denken vor allem dort, wo Datenmengen wachsen können, nicht bei jedem einzelnen Codeschnipsel.

In der Praxis muss man Algorithmen selten komplett selbst entwickeln — die meisten Standardprobleme (Sortieren, Suchen, kürzeste Wege in Graphen) sind bereits in Standardbibliotheken effizient implementiert. Wichtiger als das Auswendiglernen konkreter Algorithmen ist zu verstehen, WARUM ein Ansatz schneller ist als ein anderer, um die richtige Bibliotheksfunktion oder Datenstruktur für die eigene Situation auszuwählen.

Zeit- vs. Speicherkomplexität

Big-O beschreibt meist die Zeitkomplexität (wie viele Rechenschritte), aber genauso wichtig ist die Speicherkomplexität (wie viel zusätzlicher Speicher gebraucht wird) — beide stehen oft in einem Zielkonflikt (“Time-Space-Tradeoff”). Ein Algorithmus, der Zwischenergebnisse zwischenspeichert (Memoization, siehe Rekursion), tauscht Speicherverbrauch gegen Rechenzeit ein: die Fibonacci-Folge naiv-rekursiv berechnet ist O(2ⁿ) in der Zeit, mit einem einfachen Cache der bereits berechneten Werte wird daraus O(n) Zeit bei O(n) zusätzlichem Speicher.

Greedy vs. dynamische Programmierung

Zwei verbreitete algorithmische Strategien lösen Optimierungsprobleme sehr unterschiedlich:

• Greedy (gierig): Trifft in jedem Schritt die lokal beste Entscheidung, ohne spätere Konsequenzen zu berücksichtigen — schnell und einfach zu implementieren, liefert aber nicht immer das global beste Ergebnis (z. B. beim Münzwechsel-Problem mit ungünstigen Münzwerten).
• Dynamische Programmierung: Zerlegt das Problem in überlappende Teilprobleme und speichert deren Lösungen, um sie nicht mehrfach neu zu berechnen — liefert garantiert die optimale Lösung, ist aber komplexer zu entwerfen und braucht mehr Speicher.

# Greedy: bei jedem Schritt die größte passende Münze nehmen
# funktioniert für Standardwährung (1,2,5,10,20,50), aber nicht für jede Münzmenge
wechselgeld_greedy(betrag, muenzen_absteigend_sortiert)
 
# Dynamische Programmierung: alle Teilbeträge einmal berechnen und wiederverwenden
wechselgeld_dp(betrag, muenzen)  # garantiert optimal, mehr Aufwand

Stabilität bei Sortieralgorithmen

Ein oft übersehenes Detail bei Sortieralgorithmen: Stabilität bedeutet, dass Elemente mit gleichem Sortierschlüssel ihre ursprüngliche Reihenfolge zueinander behalten. Das ist wichtig, wenn man z. B. erst nach Nachname, dann nach Vorname sortiert — eine instabile Sortierung könnte die Nachname-Sortierung beim zweiten Sortiervorgang durcheinanderwerfen. Merge Sort ist von Natur aus stabil, Quick Sort in seiner klassischen Form nicht.

Praktische Auswirkung in Zahlen

Der Unterschied zwischen Komplexitätsklassen ist keine akademische Spielerei: Bei 1 Million Einträgen braucht ein O(n²)-Algorithmus (z. B. Bubble Sort) in der Größenordnung von 10¹² Operationen, ein O(n log n)-Algorithmus (Merge Sort) dagegen nur etwa 2×10⁷ — ein Faktor von rund 50.000. Genau deshalb reagieren scheinbar harmlose, verschachtelte Schleifen über große Datenmengen (z. B. “für jedes Element, suche in der ganzen Liste”) oft erst bei echten Produktionsdaten spürbar langsam, obwohl sie im Test mit wenigen Einträgen völlig unauffällig liefen.

Siehe auch: Sorting, Data Structures, Recursion