Wie schnell ist ein Programm?

Warum lädt eine App sofort, während eine andere ewig rödelt? Oft liegt es nicht am Handy, sondern daran, wie schlau das Programm rechnet. Beim Suchen und Sortieren hast du schon Schritte gezählt. Jetzt machen wir daraus eine richtige Superkraft: Du lernst vorherzusagen, wie sich ein Programm verhält, wenn die Daten wachsen.

Schritte statt Sekunden

Sekunden zu messen ist unfair: Auf einem schnellen Rechner läuft dasselbe Programm schneller als auf einem alten Handy. Deshalb zählen Informatikerinnen und Informatiker lieber Schritte, zum Beispiel Vergleiche. Die Anzahl der Schritte ist auf jedem Gerät gleich. So kannst du zwei Verfahren vergleichen, ohne sie überhaupt laufen zu lassen.

Wie wächst der Aufwand mit n?

Die spannende Frage ist nicht, wie viele Schritte ein Programm bei 10 Einträgen braucht, sondern was passiert, wenn aus 10 Einträgen 10000 werden. Die Eingabegröße nennen wir n. Bei der linearen Suche wächst die Schrittzahl direkt mit n: doppelt so viele Einträge, doppelt so viele Schritte. Bei der binären Suche kommt pro Verdopplung von n nur ein einziger Schritt dazu, weil jeder Schritt die Liste halbiert. Wichtig: Halbieren funktioniert nur, wenn die Liste sortiert ist.

Linear gegen Halbieren

Bei einer Liste mit 8 Einträgen ist der Unterschied winzig: 8 Schritte gegen 3 Schritte, wen kümmert das? Aber lass n wachsen. Bei 1024 Einträgen steht es 1024 gegen 10. Bei einer Million Einträgen etwa eine Million gegen 20. Das halbierende Verfahren wächst so langsam, dass selbst riesige Eingaben kaum ins Gewicht fallen. Dieses Wachstumsverhalten nennt man logarithmisch.

Warum das alles entscheidet

Suchmaschinen, Kartendienste und Streaminganbieter arbeiten mit Milliarden von Einträgen. Bei solchen Größen entscheidet das Wachstumsverhalten darüber, ob eine Antwort in Millisekunden kommt oder erst nach Stunden. Ein schnellerer Rechner hilft nur ein bisschen, ein besseres Verfahren hilft gewaltig. Deshalb ist das Zählen von Schritten eine der wichtigsten Ideen der Informatik.