Welche formalen Eigenschaften definieren einen Algorithmus?
Die drei Grundpfeiler eines Algorithmus
Du weißt bereits, dass ein Algorithmus eine präzise Schritt-für-Schritt-Anleitung zur Lösung eines Problems ist. Damit ein Computer diese Vorschrift jedoch fehlerfrei abarbeiten kann, muss sie drei strenge formale Kriterien erfüllen:
- Finitheit (Endlichkeit): Der Algorithmus muss nach einer endlichen Anzahl von Schritten garantiert zum Abschluss kommen und ein Ergebnis liefern. Eine unbeabsichtigte Endlosschleife (die du bereits kennengelernt hast) verletzt dieses Prinzip.
- Determinismus (Eindeutigkeit): Bei exakt gleicher Eingabe muss der Algorithmus stets denselben Weg durchlaufen und exakt dasselbe Ergebnis produzieren. Jeder einzelne Schritt muss unmissverständlich definiert sein, ohne Raum für Interpretationen.
- Ausführbarkeit: Jeder Schritt muss für den Computer prinzipiell lösbar und mit den verfügbaren Basisoperationen (wie Addition, Zuweisung oder Vergleich) durchführbar sein.
Ressourcenbedarf: Zeit- und Speicherkomplexität
Ein Algorithmus kann formal völlig korrekt sein, in der Praxis aber scheitern, weil er zu viele Ressourcen verbraucht. Wir bewerten die Effizienz anhand von zwei zentralen Metriken:
- Zeitkomplexität: Sie misst nicht die absolute Dauer in Sekunden, da diese stark von der verwendeten Hardware abhängt. Stattdessen zählt sie die Anzahl der grundlegenden Rechenoperationen in Abhängigkeit von der Größe der Eingabedaten.
- Speicherkomplexität: Sie beschreibt den zusätzlichen Arbeitsspeicher (RAM), den der Algorithmus während seiner Ausführung benötigt, unabhängig vom Speicherplatz der eigentlichen Eingabedaten.
Stell dir vor, du suchst einen Namen in einer unsortierten Liste mit einer Million Einträgen. Jeder Eintrag muss einzeln geprüft werden (hohe Zeitkomplexität). Ist die Liste jedoch sortiert, kannst du den Suchbereich in jedem Schritt halbieren – das reduziert die benötigten Rechenoperationen massiv.
Wie vergleichen wir die Effizienz mit der Big O-Notation?
Die Big O-Notation: Fokus auf das Wachstum
Um Algorithmen objektiv vergleichen zu können, nutzen wir die Big O-Notation (z. B. O(n)). Sie beschreibt das asymptotische Wachstumsverhalten eines Algorithmus im schlechtesten Fall (Worst-Case).
Die Kernfrage lautet: Wie stark steigt die Laufzeit oder der Speicherbedarf an, wenn die Datenmenge n immer größer wird? Dabei ignorieren wir konstante Faktoren oder die Taktfrequenz des Prozessors. Uns interessiert nur der dominante Trend. Ein Algorithmus, dessen Laufzeit linear mit den Daten wächst, wird bei riesigen Datenmengen immer einen Algorithmus schlagen, dessen Laufzeit quadratisch wächst – völlig unabhängig davon, wie schnell der ausführende Computer ist.
Effiziente Komplexitätsklassen: Konstant bis Linear
Je flacher die visualisierte Wachstumskurve bei steigenden Datenmengen verläuft, desto besser skaliert der Algorithmus:
- O(1) – Konstante Komplexität: Die Laufzeit ist immer gleich, egal wie groß
nist. Ein klassisches Beispiel ist der direkte Index-Zugriff auf ein Element in einem Array.
def get_first(liste):
# Dauert immer gleich lang, egal ob 10 oder 10.000 Elemente
return liste[0] - O(log n) – Logarithmische Komplexität: Die Laufzeit wächst extrem langsam. Verdoppelt sich die Datenmenge, kommt nur ein einziger Rechenschritt hinzu. Dies ist typisch für Algorithmen, die das Problem in jedem Schritt halbieren (z. B. die binäre Suche).
- O(n) – Lineare Komplexität: Die Laufzeit wächst direkt proportional zur Datenmenge.
def print_all(liste):
# Bei n Elementen wird die Schleife exakt n-mal durchlaufen
for item in liste:
print(item)Ineffiziente Klassen: Quadratisch und Exponentiell
Bei diesen Komplexitätsklassen führt eine Erhöhung der Datenmenge zu einer regelrechten Explosion der benötigten Rechenzeit. Sie sollten bei großen Datenmengen vermieden werden:
- O(n²) – Quadratische Komplexität: Die Laufzeit wächst mit dem Quadrat der Eingabemenge. Dies passiert typischerweise bei verschachtelten Schleifen. Bei 1.000 Elementen sind bereits 1.000.000 Operationen nötig.
def print_pairs(liste):
for i in liste:
# Verschachtelung führt zu n * n Durchläufen
for j in liste:
print(i, j)- O(2^n) – Exponentielle Komplexität: Mit jedem einzelnen neuen Element in der Eingabe verdoppelt sich die Laufzeit. Solche Algorithmen (z. B. das Ausprobieren aller möglichen Kombinationen beim Knacken eines Passworts durch Brute-Force) sind für reale, große Datenmengen in der Praxis unbrauchbar, da sie selbst auf Supercomputern Jahre dauern würden.
Teste dein Wissen
Du schreibst ein Skript zur Logfile-Analyse. Durch einen Fehler fehlt die Abbruchbedingung in einer Schleife. Welches formale Kriterium eines Algorithmus wird hier verletzt?