Zeitkomplexität

Ein Computer arbeitet eine Aufgabe in einzelnen Schritten ab. Wie viele Schritte er braucht, hängt fast immer davon ab, wie viele Daten er bekommt. Ein Name in einer Liste von zehn Einträgen ist schnell gefunden, in einer Liste von zehn Millionen dauert es länger. Die Zeitkomplexität beschreibt genau diesen Zusammenhang: Sie sagt, wie stark der Aufwand wächst, wenn die Datenmenge wächst. Sie misst also keine Sekunden, sondern das Wachstumsverhalten. Damit kann man zwei Lösungswege vergleichen, ohne sie überhaupt auf einem Computer auszuprobieren.

Warum zehnmal mehr Daten selten zehnmal mehr Zeit bedeuten

Rechner werden jedes Jahr schneller, aber Datenmengen wachsen noch schneller. Deshalb entscheidet nicht die rohe Geschwindigkeit, ob ein Programm brauchbar ist. Entscheidend ist, wie es auf mehr Daten reagiert. Ein Verfahren, dessen Aufwand sich bei doppelter Datenmenge vervierfacht, ist bei kleinen Tests unauffällig. Im echten Betrieb mit Millionen Einträgen bricht es zusammen.

Ein Beispiel macht das greifbar. Sortiert man eine Liste, indem man jedes Element mit jedem anderen vergleicht, braucht man bei 1.000 Elementen rund eine Million Vergleiche. Ein gutes Sortierverfahren kommt mit etwa 10.000 Vergleichen aus. Bei 1.000 Elementen merkt man den Unterschied kaum. Bei einer Million Elementen ist das schlechte Verfahren praktisch unbenutzbar, während das gute in Sekundenbruchteilen fertig ist.

Ein häufiger Irrtum: Eine schlechte Zeitkomplexität lässt sich nicht durch bessere Hardware ausgleichen. Doppelt so schnelle Rechner halbieren die Zeit ein einziges Mal. Ein besseres Verfahren verändert dagegen die Kurve selbst und wirkt bei jeder Datenmenge erneut.

Was das große O bedeutet

Fachleute schreiben Zeitkomplexität mit einem großen O und der Datenmenge n. O(n) heißt: Der Aufwand wächst proportional zur Datenmenge. Zehnmal mehr Daten bedeuten zehnmal mehr Arbeit. Das gilt zum Beispiel, wenn man eine unsortierte Liste einmal komplett durchgeht.

O(n²) heißt: Bei zehnmal mehr Daten wächst der Aufwand auf das Hundertfache. Das passiert, wenn man jedes Element mit jedem vergleicht. O(log n) ist der angenehme Fall: Der Aufwand wächst nur sehr langsam. So funktioniert die Suche in einem sortierten Verzeichnis, bei der man den Suchbereich immer wieder halbiert. Aus einer Million Einträgen findet man den richtigen mit etwa zwanzig Schritten.

Wichtig ist, was diese Schreibweise absichtlich weglässt. Konstante Faktoren und kleine Zusatzschritte werden ignoriert. Ein O(n)-Verfahren kann bei kleinen Datenmengen langsamer sein als ein O(n²)-Verfahren. Die O-Notation beschreibt nur, wer bei großen Mengen gewinnt. Meist gibt man außerdem den ungünstigsten Fall an, damit man eine verlässliche Obergrenze hat.

Zeitkomplexität in KI-Modellen und in Bewerbungsgesprächen

Bei Sprachmodellen taucht das Thema an einer sehr konkreten Stelle auf. Der wichtigste Baustein dieser Modelle vergleicht jedes Wort einer Eingabe mit jedem anderen Wort. Das ist ein klassischer O(n²)-Fall. Verdoppelt man die Länge des Textes, vervierfacht sich der Rechenaufwand. Deshalb war es lange teuer, einem Chatbot ein ganzes Buch vorzulegen.

Genau darum arbeiten Forschungsgruppen an Verfahren, die diesen Vergleich abkürzen. Wenn in News steht, ein Modell verarbeite nun ein Kontextfenster von einer Million Zeichen, steckt fast immer eine solche Verbesserung dahinter. Auch in Datenbanken ist das Thema allgegenwärtig: Ein Index sorgt dafür, dass eine Suche nicht die gesamte Tabelle durchläuft, sondern in wenigen Schritten fertig ist.

Für Programmiererinnen und Programmierer gehört Zeitkomplexität zum Grundwissen. In Einstellungsgesprächen bei Technikfirmen ist die Frage nach der Laufzeit einer Lösung Standard. Wer nur eine funktionierende Antwort liefert, aber nicht sagen kann, wie sie bei einer Million Datensätzen skaliert, hat die Aufgabe nur halb gelöst.