O-Notation – Anweisungen zählen

Worum geht es?

Die O-Notation beschreibt, wie der Rechenaufwand eines Programms mit der Eingabegröße n wächst. Um sie zu bestimmen, zählen wir zuerst, wie viele Anweisungen ein Programm tatsächlich ausführt – und vereinfachen diese Zahl danach zu einer Wachstumsklasse.

So zählen wir die ausgeführten Zeilen

Jede Zeile im Schleifen- oder Funktionskörper zählt – so oft, wie sie wirklich ausgeführt wird.
Kopfzeilen werden nicht gezählt: for ...:, while ...:, if ...:, def ...: steuern nur den Ablauf, sie sind nicht die eigentliche Arbeit.
Eine Zeile, die in einer Schleife steht, die n-mal läuft, zählt n-mal.
Stehen zwei Schleifen nacheinander, werden ihre Schritte addiert. Stehen sie ineinander (verschachtelt), werden sie multipliziert.

Vom Zählen zur O-Notation

Wenn die Gesamtzahl der Anweisungen feststeht, vereinfachen wir in zwei Schritten:

Konstante Faktoren weglassen: aus 2·n + 2 wird O(n), aus n²/2 wird O(n²).
Nur den am schnellsten wachsenden Term behalten: aus 3n² + 5n + 7 wird O(n²).

Merksatz: Erst genau zählen (wie oft läuft jede Körperzeile?), dann grob vereinfachen (Konstanten und kleine Terme weg). Unten siehst du beide Schritte live.

Zeilen zählen

Wähle ein Programm und schiebe n. Graue Zeilen sind Kopfzeilen und zählen nicht mit. Die blaue Markierung zeigt, wie oft jede Körperzeile bei diesem n ausgeführt wird.

Programm

Eingabegröße n = 6

Ausgeführte Anweisungen

–

Allgemein: –

Wächst wie –

Aufwand bei diesem n

Dein Punktestand 0 / 0

Multiple-Choice-Übungen

Zähle bei jedem Programm zuerst selbst die ausgeführten Anweisungen (Kopfzeilen weglassen!) und wähle dann die richtige Antwort. Nach dem Klick erscheint die Erklärung.

Spickzettel: die wichtigsten Klassen

Klasse	Name	Typisches Muster	Aufwand bei n = 1000
O(1)	konstant	feste Anzahl Anweisungen, keine Schleife über n	1
O(log n)	logarithmisch	n wird jede Runde halbiert (`while n > 1`)	≈ 10
O(n)	linear	eine Schleife über n (auch mehrere nacheinander)	1000
O(n log n)	fast linear	Halbieren plus Durchlauf, z. B. Merge Sort	≈ 10 000
O(n²)	quadratisch	zwei verschachtelte Schleifen über n	1 000 000
O(2ⁿ)	exponentiell	jeder Schritt verdoppelt die Möglichkeiten	astronomisch

Lust, die Programme selbst laufen zu lassen? Tippe sie in WebTigerPython ein und baue einen Zähler ein, der bei jeder ausgeführten Körperzeile um 1 erhöht wird – so prüfst du deine Handzählung nach.