Algorithmen & Datenstrukturen

Bei zehn Datensätzen ist fast jede Lösung schnell genug. Der Unterschied zwischen einem geschickten und einem naiven Verfahren wird erst sichtbar, wenn die Datenmenge wächst — und dann oft schlagartig. Genau deshalb betrachtet die Informatik nicht die Laufzeit in Sekunden, sondern das Wachstumsverhalten: Wie verändert sich der Aufwand, wenn sich die Eingabe verzehnfacht?

Diese Sichtweise ist bewusst grob. Konstante Faktoren, Prozessorgeschwindigkeit und Programmiersprache spielen für sie keine Rolle, weil sie an der grundsätzlichen Skalierung nichts ändern. Ein Verfahren, dessen Aufwand quadratisch wächst, wird auf schnellerer Hardware zwar später, aber genauso sicher zum Problem.

Ebenso wichtig ist die Unterscheidung von günstigem, typischem und ungünstigem Fall. Manche Verfahren sind im Mittel hervorragend und im schlechtesten Fall schwach. Ob das akzeptabel ist, hängt vom Einsatz ab: Bei einer internen Auswertung stört ein seltener Ausreißer kaum, bei einer Anfrage im Live-Betrieb sehr wohl.

Hinter den unzähligen benannten Algorithmen stecken einige wenige Grundstrategien. Teile und herrsche zerlegt ein Problem in kleinere gleichartige Teilprobleme und setzt die Teillösungen zusammen — das Prinzip hinter effizientem Sortieren und der binären Suche. Gierige Verfahren treffen in jedem Schritt die lokal beste Entscheidung und sind schnell, aber nicht immer optimal.

Dynamische Programmierung merkt sich bereits berechnete Zwischenergebnisse und vermeidet so, dieselbe Teilaufgabe hundertfach zu lösen. Graphverfahren beantworten Fragen nach Wegen, Erreichbarkeit und kürzesten Verbindungen — von der Navigation über Abhängigkeiten in Bauprozessen bis zu Freundschaftsempfehlungen.

Daneben steht der Werkzeugkasten der Datenstrukturen, denn Verfahren und Struktur bedingen einander. Ein Array erlaubt schnellen Zugriff über den Index, eine verkettete Liste günstiges Einfügen, eine Hashtabelle sehr schnelles Nachschlagen ohne Ordnung, ein Suchbaum sortierte Zugriffe und Bereichsabfragen, eine Warteschlange mit Priorität den jeweils dringendsten Eintrag. Die passende Struktur ersetzt oft den cleveren Algorithmus.

Nur wenige Entwickler implementieren ein Sortierverfahren selbst — Standardbibliotheken sind ausgereift und meist schneller als handgeschriebener Code. Der Nutzen liegt woanders: im Erkennen, welche Operation im aktuellen Kontext teuer ist. Eine Suche in einer Liste innerhalb einer Schleife, eine Datenbankabfrage pro Datensatz statt einer verknüpften Abfrage, wiederholtes Neuberechnen unveränderter Werte — das sind die realen Fälle.

Auch die Werkzeuge, die man täglich benutzt, beruhen auf diesen Ideen: Datenbankindizes sind Suchbäume, Zwischenspeicher nutzen Hashtabellen, Versionsverwaltungen vergleichen Bäume, Kompression und Verschlüsselung sind Algorithmen in Reinform.

Zum Lernen eignen sich kleine, gut abgegrenzte Aufgaben besser als lange Theoriekapitel. Ein Verfahren von Hand auf Papier durchzuspielen, bevor man es programmiert, deckt Verständnislücken zuverlässiger auf als jede Erklärung — und macht anschließend die Notation für den Aufwand von selbst plausibel.

Bevor sich die Frage nach dem Aufwand überhaupt lohnt, muss ein Verfahren verlässlich das Richtige tun — und daran scheitern Umsetzungen häufiger als an der Laufzeit. Die üblichen Verdächtigen sind Randfälle: die leere Eingabe, ein einziges Element, doppelte Werte, bereits sortierte oder genau umgekehrt sortierte Daten, negative Zahlen. Wer diese Fälle bewusst durchgeht, findet die meisten Fehler, bevor jemand anders sie findet.

Dazu kommen Eigenheiten der Maschine. Ganzzahlen haben in vielen Sprachen einen begrenzten Wertebereich, und Kommazahlen werden binär nur angenähert — deshalb prüft man sie nie auf Gleichheit, sondern auf einen ausreichend kleinen Abstand. Auch Rekursion hat eine Grenze: Jeder Aufruf belegt Platz auf dem Aufrufstapel, weshalb tiefe Rekursion bei großen Eingaben abbricht und dort besser durch eine Schleife ersetzt wird.

Hilfreich ist der Begriff der Invariante — eine Aussage, die vor und nach jedem Schritt gilt, etwa dass ein bestimmter Abschnitt der Liste stets sortiert ist. Wer sie benennen kann, hat ein Verfahren verstanden; wer sie prüft, findet Fehler dort, wo sie entstehen, statt am Ergebnis.