Aufwand von Algorithmen: Wachstum und O-Notation

Zwei Programme lösen dieselbe Aufgabe. Bei 100 Datensätzen sind beide sofort fertig. Bei einer Million braucht das eine eine Sekunde und das andere elf Tage.

Der Unterschied liegt nicht an der Sprache, nicht am Rechner und nicht an der Sorgfalt beim Programmieren. Er liegt daran, wie der Aufwand mit der Datenmenge wächst.

Genau das ist die Frage dieses Kapitels, und sie ist eine andere als im vorigen. Dort ging es darum, ob eine Lösung überhaupt existiert. Hier ist die Existenz gesichert, und es geht darum, ob sie brauchbar ist.

Vorausgesetzt werden Schleifen und Verschachtelung aus Algorithmen entwerfen sowie die Algorithmusmerkmale aus Was ist ein Algorithmus?.

Neu ist die Frage nach dem Preis eines Verfahrens, und der wird nicht in Sekunden gemessen.

Naheliegend wäre, ein Programm laufen zu lassen und zu stoppen. Für einen Vergleich taugt das wenig:

• Ein anderer Rechner liefert andere Zeiten.
• Eine andere Sprache oder ein anderer Übersetzer ebenso.
• Vor allem: Die Messung gilt nur für die eine getestete Datenmenge.

Interessant ist aber gerade die Frage, was bei zehnmal so vielen Daten passiert. Deshalb misst man nicht die Zeit, sondern zählt die wesentlichen Schritte in Abhängigkeit von der Eingabegröße $n$.

Beispiel 1: lineare Suche. Gesucht wird ein Wert in einer Liste mit $n$ Einträgen:

für i von 1 bis n:
    wenn liste[i] = gesucht:
        gib i zurück
gib "nicht gefunden" zurück

Der wesentliche Schritt ist der Vergleich. Im schlechtesten Fall stehen $n$ Vergleiche an. Aufwand: linear.

Beispiel 2: alle Paare vergleichen.

für i von 1 bis n:
    für j von 1 bis n:
        vergleiche liste[i] mit liste[j]

Die innere Schleife läuft für jeden Durchlauf der äußeren komplett durch. Das ergibt $n \cdot n = n^2$ Vergleiche. Aufwand: quadratisch.

Beispiel 3: binäre Suche in einer sortierten Liste: Jeder Schritt halbiert den Suchbereich. Nach $k$ Schritten sind noch $n / 2^k$ Einträge übrig, und man ist fertig, wenn einer übrig ist:

$$\frac{n}{2^k} = 1 \quad \Longleftrightarrow \quad 2^k = n \quad \Longleftrightarrow \quad k = \log_2 n$$

Aufwand: logarithmisch. Bei einer Million Einträgen sind das rund 20 Schritte statt einer Million.

Beim Zählen stört, dass Kleinigkeiten das Bild verstellen. Ein Verfahren mit $3n^2 + 5n + 12$ Schritten ist im Kern quadratisch; die $5n$ und die $12$ fallen bei großem $n$ nicht ins Gewicht.

Deshalb schreibt man nur das Wachstumsverhalten auf:

$$3n^2 + 5n + 12 \in O(n^2)$$

Zwei Regeln genügen fast immer:

Konstante Faktoren weglassen. $3n^2$ und $n^2$ stehen beide in $O(n^2)$. Nur den am stärksten wachsenden Term behalten. $n^2 + n$ steht in $O(n^2)$.

🔴 Der Grund für die erste Regel ist wichtig und wird oft missverstanden. Man lässt Konstanten nicht weg, weil sie egal wären, sondern weil sie von Rechner, Sprache und Übersetzer abhängen und damit keine Eigenschaft des Verfahrens sind. Das Wachstumsverhalten dagegen bleibt auf jedem Rechner dasselbe.

Sieh dir an, was das praktisch heißt. Ein doppelt so schneller Rechner halbiert die Zeit, also den konstanten Faktor. Er ändert nichts daran, dass bei doppelter Datenmenge ein quadratisches Verfahren viermal so lange braucht. Genau deshalb ist die Wachstumsklasse die entscheidende Größe und nicht der Vorfaktor.

Die letzte Zeile verdient einen Moment. $2^{1000}$ hat über 300 Stellen; zum Vergleich schätzt man die Zahl der Atome im beobachtbaren Universum auf etwa $10^{80}$. Ein exponentielles Verfahren ist bei $n = 1000$ nicht „langsam", sondern grundsätzlich nicht durchführbar, und daran ändert kein technischer Fortschritt etwas.

Eine nützliche Faustregel: Jede geschachtelte Schleife über dieselben Daten erhöht den Exponenten um eins. Zwei Schleifen ineinander ergeben $O(n^2)$, drei ergeben $O(n^3)$.

Bei der linearen Suche hängt der Aufwand davon ab, wo der gesuchte Wert steht:

• Bester Fall: gleich der erste Eintrag, also $O(1)$.
• Schlechtester Fall: letzter Eintrag oder nicht vorhanden, also $O(n)$.
• Mittlerer Fall: im Schnitt die halbe Liste, also $n/2$ Schritte, und das ist ebenfalls $O(n)$, weil der Faktor $\tfrac{1}{2}$ konstant ist.

Üblicherweise gibt man den schlechtesten Fall an, und zwar aus einem klaren Grund: Er ist die einzige Angabe, die eine Garantie liefert. Ein Verfahren, das meistens schnell ist und gelegentlich sehr langsam, kann in einem Steuerungssystem oder bei einer Nutzeroberfläche untragbar sein.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Man fasst Probleme nach ihrem Aufwand zusammen:

$P$ enthält die Probleme, die sich in polynomieller Zeit lösen lassen, also mit $O(n^k)$ für ein festes $k$. Das gilt als praktisch handhabbar.

$NP$ enthält die Probleme, bei denen sich eine vorgeschlagene Lösung in polynomieller Zeit prüfen lässt.

Der Unterschied ist der zwischen finden und nachrechnen. Ein Sudoku zu lösen ist mühsam; eine ausgefüllte Lösung zu prüfen dauert Sekunden. Ein Passwort zu erraten ist aussichtslos; ein vorgeschlagenes zu prüfen ist trivial.

Klar ist: $P \subseteq NP$. Wer eine Lösung schnell finden kann, kann sie auch schnell prüfen, indem er sie selbst berechnet und vergleicht.

Offen ist die Umkehrung, und das ist die berühmteste offene Frage der Informatik:

Ist $P = NP$? Also: Ist jedes Problem, dessen Lösung sich schnell prüfen lässt, auch schnell lösbar?

Die meisten Fachleute vermuten $P \neq NP$, bewiesen ist nichts. Für einen Beweis in die eine oder andere Richtung sind eine Million Dollar ausgesetzt.

Warum das mehr als eine Denksportaufgabe ist: Ein großer Teil der heutigen Verschlüsselung beruht darauf, dass Prüfen leicht und Finden schwer ist. Wäre $P = NP$ mit einem praktisch brauchbaren Verfahren, verlöre ein Gutteil der digitalen Sicherheit ihre Grundlage. Umgekehrt ließen sich viele Optimierungsaufgaben in Logistik und Planung plötzlich exakt lösen.

🔴 Beachte den Unterschied zum vorigen Kapitel. Unentscheidbar heißt: Es gibt keine Lösung, nie. $NP$-schwer heißt: Es gibt eine Lösung, aber alle bekannten Verfahren sind für große Eingaben zu teuer. Das eine ist eine Grenze des Möglichen, das andere eine Grenze des Machbaren.