Modul 3 von 6
Algorithmen und Datenstrukturen
Ein Programm, das mit zehn Datensätzen funktioniert, kann bei zehn Millionen stillstehen. In diesem Modul lernst du, das vorher zu erkennen - und die richtige Struktur für die jeweilige Aufgabe zu wählen. Das ist die Vorlesung, die im Studium am meisten aussiebt, und zugleich die, die am meisten hängen bleibt.
1. Was ist ein Algorithmus?
Ein Algorithmus ist eine eindeutige Handlungsvorschrift, die ein Problem in endlich vielen Schritten löst. Er ist unabhängig von der Programmiersprache - man kann ihn auf einer Serviette aufschreiben.
- Eindeutigkeit: Jeder Schritt ist unmissverständlich beschrieben.
- Ausführbarkeit: Jeder Schritt ist tatsächlich durchführbar.
- Endlichkeit: Die Beschreibung ist endlich lang.
- Terminierung: Das Verfahren kommt nach endlich vielen Schritten zum Ende.
- Determiniertheit: Gleiche Eingabe führt zu gleichem Ergebnis.
"Salz nach Geschmack" verletzt die Eindeutigkeit. "Rühren, bis der Teig gut aussieht" verletzt die Terminierung - es gibt kein prüfbares Abbruchkriterium. Genau an diesen Stellen scheitern übrigens auch Anforderungen aus Fachabteilungen: "Zeig mir die wichtigsten Kunden" ist kein umsetzbarer Auftrag, "sortiere nach Jahresumsatz und zeig die obersten zehn" schon.
Pseudocode
Zum Aufschreiben von Algorithmen nutzt man Pseudocode: strukturiert wie ein Programm, aber ohne Rücksicht auf Syntax. In Klausuren wird oft genau das verlangt.
ALGORITHMUS GroesstesElement(liste)
WENN liste ist leer DANN
GIB ZURÜCK "kein Element"
groesstes ← liste[0]
FÜR i VON 1 BIS länge(liste) - 1
WENN liste[i] > groesstes DANN
groesstes ← liste[i]
GIB ZURÜCK groesstes2. Laufzeit und die O-Notation
Die entscheidende Frage bei jedem Algorithmus lautet nicht "wie viele Sekunden braucht er?", sondern "wie stark wächst der Aufwand, wenn die Datenmenge wächst?" Sekunden hängen vom Rechner ab, das Wachstumsverhalten nicht.
Einen Namen im Telefonbuch findest du in Sekunden, obwohl Millionen Einträge drinstehen - weil du aufschlägst, vergleichst und eine Hälfte wegwirfst. Würdest du stattdessen Zeile für Zeile von vorn lesen, säßest du Tage daran. Beide Male dieselben Daten, derselbe Mensch, aber ein völlig anderes Wachstumsverhalten.
Die O-Notation beschreibt genau dieses Wachstum. Konstante Faktoren werden weggelassen: Ob ein Schritt 2 oder 20 Mikrosekunden dauert, ist bei genügend großen Datenmengen egal - die Wachstumsklasse nicht.
| Klasse | Name | Bei 1 000 Elementen | Bei 1 000 000 | Beispiel |
|---|---|---|---|---|
O(1) | konstant | 1 Schritt | 1 Schritt | Zugriff auf ein Array-Element |
O(log n) | logarithmisch | ca. 10 | ca. 20 | binäre Suche |
O(n) | linear | 1 000 | 1 000 000 | eine Liste einmal durchgehen |
O(n log n) | linear-logarithmisch | ca. 10 000 | ca. 20 Mio. | gute Sortierverfahren |
O(n²) | quadratisch | 1 Million | 1 Billion | zwei verschachtelte Schleifen |
O(2ⁿ) | exponentiell | praktisch unberechenbar | alle Teilmengen durchprobieren | |
Nimm an, ein Schritt dauert eine Mikrosekunde. Bei einer Million Datensätze braucht
ein O(n)-Verfahren eine Sekunde. Ein O(n²)-Verfahren
braucht für dieselben Daten rund elfeinhalb Tage. Das ist kein Unterschied,
den man mit einem schnelleren Server behebt.
Wie man die Klasse abliest
Eine brauchbare Faustregel für Klausuren:
- Keine Schleife, nur ein paar Rechnungen →
O(1) - Eine Schleife über alle n Elemente →
O(n) - Eine Schleife in einer Schleife, beide über n →
O(n²) - Der Suchbereich halbiert sich in jedem Schritt →
O(log n) - Halbieren und jede Ebene einmal durchgehen →
O(n log n)
3. Suchen: linear und binär
Lineare Suche
Von vorn anfangen und jedes Element prüfen. Funktioniert immer, auch bei unsortierten
Daten. Aufwand: O(n).
Binäre Suche
Setzt sortierte Daten voraus. Man schaut in die Mitte, vergleicht und
verwirft die Hälfte, in der der gesuchte Wert nicht liegen kann. Aufwand:
O(log n).
Gesucht: 23 in [4, 8, 15, 16, 23, 42, 50, 68]
Schritt 1: Mitte ist 16. 23 > 16 → rechte Hälfte behalten
[23, 42, 50, 68]
Schritt 2: Mitte ist 50. 23 < 50 → linke Hälfte behalten
[23, 42]
Schritt 3: Mitte ist 23. gefunden!
3 Schritte statt 5 bei linearer Suche.Bei einer Million sortierter Einträge braucht die binäre Suche höchstens 20 Schritte. Bei einer Milliarde sind es 30. Jede Verdopplung der Datenmenge kostet genau einen zusätzlichen Schritt. Das ist der Grund, warum Datenbanken Indizes anlegen - ein Index ist nichts anderes als eine sortierte Struktur, in der sich binär suchen lässt.
Binäre Suche ist nur schneller, wenn die Daten bereits sortiert sind. Einmal
sortieren kostet O(n log n) - mehr als eine einzelne lineare Suche.
Die Faustregel: Wird die Liste oft durchsucht und selten geändert, lohnt sich
das Sortieren. Bei einer einmaligen Suche lohnt es sich nicht.
4. Sortierverfahren
Sortieren ist das Standardbeispiel der Algorithmik, weil sich daran alles zeigen lässt: verschiedene Ansätze für dasselbe Problem, mit messbar unterschiedlichem Aufwand. Wähl unten ein Verfahren und sieh ihm zu.
- Bei Bubblesort wandert der größte Wert in jedem Durchlauf ganz nach rechts - der grüne Bereich wächst von hinten.
- Bei Insertionsort ist der linke Teil immer schon sortiert; jedes neue Element wird hineingeschoben.
- Bei Quicksort siehst du, wie sich um den Trennwert herum zwei Bereiche bilden, die dann getrennt weiterbearbeitet werden.
- Vergleich die Zähler: Stell 50 Balken ein und schau, wie viele Vergleiche Bubblesort gegenüber Quicksort braucht.
| Verfahren | Mittel | Schlechtester Fall | Stabil? | Wann sinnvoll |
|---|---|---|---|---|
| Bubblesort | O(n²) | O(n²) | ja | nur zum Lernen |
| Selectionsort | O(n²) | O(n²) | nein | wenn Vertauschen teuer ist |
| Insertionsort | O(n²) | O(n²) | ja | kleine oder fast sortierte Mengen |
| Mergesort | O(n log n) | O(n log n) | ja | wenn garantierte Laufzeit zählt |
| Quicksort | O(n log n) | O(n²) | nein | Standardfall in der Praxis |
Ein Sortierverfahren heißt stabil, wenn Elemente mit gleichem Schlüssel ihre ursprüngliche Reihenfolge behalten. Beispiel: Du sortierst eine Kundenliste erst nach Name, dann nach Ort. Bei einem stabilen Verfahren stehen die Kunden innerhalb jedes Orts weiterhin alphabetisch. Bei einem instabilen ist diese Ordnung dahin. Genau deshalb ist Stabilität in Berichten und Auswertungen wichtig.
5. Array und verkettete Liste
Eine Datenstruktur legt fest, wie Daten im Speicher angeordnet sind. Diese Anordnung entscheidet, welche Operationen schnell sind und welche nicht.
Alle Elemente liegen direkt hintereinander im Speicher. Aus der Startadresse und dem Index lässt sich jede Adresse sofort ausrechnen.
Zugriff per Index: O(1)
Einfügen in der Mitte: O(n) - alles dahinter muss verschoben werden
Die Elemente liegen verstreut. Jedes enthält neben seinem Wert einen Verweis auf das nächste. Man muss der Kette folgen.
Zugriff per Index: O(n)
Einfügen an bekannter Stelle: O(1) - nur zwei Verweise umhängen
Es gibt keine beste Datenstruktur, nur passende. Ein Array ist schnell im Lesen und langsam im Einfügen, eine verkettete Liste genau umgekehrt. Welche du wählst, hängt davon ab, was dein Programm überwiegend tut - und diese Frage stellst du dir am besten, bevor du anfängst zu programmieren.
6. Stack und Queue
Zwei Strukturen, die sich nur darin unterscheiden, an welchem Ende Elemente herauskommen - und die dadurch völlig verschiedene Aufgaben lösen.
Wie ein Stapel Teller: Der zuletzt abgelegte kommt zuerst wieder herunter.
Wo er steckt: die Rückgängig-Funktion in jedem Programm, der Zurück-Knopf
im Browser, die Verwaltung von Funktionsaufrufen im Computer (deshalb heißt es
"Stack Overflow", wenn sich eine Funktion endlos selbst aufruft).
Wie die Schlange an der Kasse: Wer zuerst kam, wird zuerst bedient.
Wo sie steckt: Druckaufträge, eingehende Bestellungen, Nachrichten zwischen
Systemen. In SAP-Landschaften laufen fast alle Schnittstellen über Queues, damit
bei einem Systemausfall nichts verloren geht.
7. Bäume und Hashtabellen
Bäume
Ein Baum ordnet Daten hierarchisch: eine Wurzel, darunter Knoten, ganz unten Blätter. Im binären Suchbaum gilt für jeden Knoten: links stehen kleinere Werte, rechts größere.
50
/ \
30 70
/ \ / \
20 40 60 80
Suche nach 40: 50 → zu klein, nach links
30 → zu groß, nach rechts
40 → gefunden. Drei Vergleiche.
Solange der Baum ausgeglichen ist, kostet Suchen, Einfügen und Löschen jeweils
O(log n). Datenbankindizes verwenden eine Weiterentwicklung davon,
den B-Baum - bei einer Tabelle mit Millionen Zeilen führt er in einer
Handvoll Schritten zum Ziel.
Fügt man in einen einfachen Suchbaum bereits sortierte Daten ein (1, 2, 3, 4, …),
hängt jeder Knoten rechts am vorigen - der Baum wird zur Liste und die Suche fällt
auf O(n) zurück. Deshalb gibt es selbstbalancierende Bäume, die
sich beim Einfügen automatisch neu ordnen.
Hashtabellen
Die schnellste Struktur zum Nachschlagen. Eine Hashfunktion rechnet
aus dem Schlüssel direkt die Speicherstelle aus - ohne jedes Suchen. Aufwand:
O(1) im Mittel.
Zwei verschiedene Schlüssel können auf dasselbe Fach zeigen. Das ist unvermeidlich
und kein Fehler - man hängt die Werte dann im Fach aneinander. Erst wenn zu viele
Kollisionen auftreten, sinkt die Geschwindigkeit von O(1) Richtung
O(n). Eine gute Hashfunktion verteilt deshalb möglichst gleichmäßig.
| Struktur | Suchen | Einfügen | Sortiert? |
|---|---|---|---|
| Array (unsortiert) | O(n) | O(1) am Ende | nein |
| Array (sortiert) | O(log n) | O(n) | ja |
| Verkettete Liste | O(n) | O(1) | nein |
| Ausgeglichener Baum | O(log n) | O(log n) | ja |
| Hashtabelle | O(1) | O(1) | nein |
Brauchst du die Daten in Reihenfolge? Dann Baum. Willst du nur möglichst schnell nachschlagen? Dann Hashtabelle. Das ist der eine Unterschied, auf den es in der Praxis meistens hinausläuft.
Übungen
Aufgabe 1 · leicht
Welche Komplexitätsklasse hat dieser Code?
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
summe += i * j;
}
}Lösung anzeigen
O(n²). Die äußere Schleife läuft n mal, die innere für jeden
Durchlauf noch einmal n mal - zusammen n · n Durchläufe.
Aufgabe 2 · leicht
Und diese hier?
let i = n;
while (i > 1) {
i = i / 2;
}Lösung anzeigen
O(log n). In jedem Durchlauf halbiert sich i. Von 1 000 000 kommt man
in etwa 20 Schritten unter 1 - genau das beschreibt der Logarithmus zur Basis 2.
Aufgabe 3 · mittel
Ein Verfahren braucht für 1000 Datensätze 2 Sekunden. Wie lange braucht es für 4000
Datensätze, wenn es O(n) ist - und wie lange, wenn es O(n²)
ist?
Lösung anzeigen
O(n): Die Datenmenge vervierfacht sich, also vervierfacht sich die Zeit: 8 Sekunden.
O(n²): Die Zeit wächst mit dem Quadrat. Vierfache Datenmenge bedeutet 4² = 16-fache Zeit: 32 Sekunden. Bei 40 000 Datensätzen wären es schon über eine halbe Stunde.
Aufgabe 4 · mittel
Implementiere die binäre Suche. Gib den Index des gesuchten Werts zurück, oder -1, wenn er nicht vorkommt.
Lösung anzeigen
function binaereSuche(liste, ziel) {
let links = 0;
let rechts = liste.length - 1;
while (links <= rechts) {
const mitte = Math.floor((links + rechts) / 2);
if (liste[mitte] === ziel) return mitte;
if (liste[mitte] < ziel) links = mitte + 1;
else rechts = mitte - 1;
}
return -1;
}
Die drei klassischen Fallen: <= statt < in
der Schleifenbedingung (sonst wird das letzte Element nie geprüft);
mitte + 1 und mitte - 1 statt mitte (sonst
Endlosschleife); und das Abrunden mit Math.floor.
Aufgabe 5 · schwer
Eine Anwendung verwaltet 5 Millionen Artikel. Sie muss sehr häufig einen Artikel anhand seiner Artikelnummer finden und außerdem regelmäßig alle Artikel nach Preis sortiert ausgeben. Welche Datenstrukturen wählst du?
Lösung anzeigen
Die beiden Anforderungen widersprechen sich - also nimmt man beides:
- Eine Hashtabelle mit der Artikelnummer als Schlüssel für das Nachschlagen
in
O(1). - Zusätzlich einen ausgeglichenen Suchbaum (oder ein sortiertes Array), geordnet nach Preis, für die sortierte Ausgabe.
Beide verweisen auf dieselben Artikelobjekte, die Daten liegen also nur einmal im Speicher. Der Preis dafür: Bei jeder Änderung müssen beide Strukturen gepflegt werden. Genau das macht eine Datenbank, wenn du einen zweiten Index anlegst - Lesen wird schneller, Schreiben etwas langsamer. Diese Abwägung begegnet dir in Modul 4 wieder.
Selbsttest
Karteikarten zu diesem Modul
Wenn du tiefer einsteigen willst
- visualgo.net - Animationen zu praktisch jedem Verfahren, das im Studium vorkommt. Nach dieser Seite die beste Anlaufstelle zum Nachschauen.
- "Algorithmen und Datenstrukturen" von Thomas Ottmann und Peter Widmayer - das deutschsprachige Standardwerk.
- "Grokking Algorithms" von Aditya Bhargava - erklärt mit Zeichnungen statt Formeln. Gut geeignet, wenn dir die Vorlesung zu formal wird.