Lektion 1.1

Laufzeit messen: Operationen zählen und O-Notation

30 min Lesezeit

Du hast zwei Programme, die dasselbe Problem lösen. Welches ist besser? Die Stoppuhr ist eine schlechte Antwort: Das Ergebnis hängt vom Rechner, vom Compiler und davon ab, was nebenbei läuft. Außerdem sagt eine Messung bei $1000$ Eingaben nichts darüber, was bei einer Million passiert.

Die Informatik misst deshalb nicht Sekunden, sondern zählt Grundoperationen (Vergleiche, Zuweisungen, Rechenschritte) in Abhängigkeit von der Eingabegröße $n$ . Und weil es bei großen $n$ nur auf die Wachstumsart ankommt, vergisst man Konstanten und Nebenglieder. Das Ergebnis ist die O-Notation: eine grobe, aber maschinenunabhängige Sprache für die Frage „Wie schnell wächst der Aufwand, wenn die Eingabe größer wird?"

Beispiel

Operationen in Schleifen zählen

Betrachte zwei verschachtelte Schleifen, wie sie in Sortieralgorithmen vorkommen: Die äußere Schleife läuft für $i = 0, \dots, n-1$ , die innere für $j = 0, \dots, i-1$ , und im Inneren steht ein Vergleich. Wie oft wird verglichen?

Für $i = 0$ gar nicht, für $i = 1$ einmal, für $i = 2$ zweimal, und so weiter bis $i = n-1$ mit $n-1$ Vergleichen. Die Summe ist die Gaußsche Summenformel:

0 + 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}

Für $n = 10$ sind es $45$ Vergleiche, für $n = 1000$ schon $499\,500$ , und für $n = 10^6$ etwa $5 \cdot 10^{11}$ . Verzehnfachst du $n$ , wächst die Zahl der Vergleiche etwa um den Faktor $100$ . Das ist die Signatur eines quadratischen Aufwands.

Definition

O-Notation (obere Schranke)

Seien $f$ und $g$ Funktionen von den natürlichen Zahlen in die nichtnegativen reellen Zahlen. Man sagt $f$ liegt in $O(g)$ , wenn es eine Konstante $c > 0$ und eine Schwelle $n_0$ gibt, sodass ab dieser Schwelle $f$ höchstens so groß wie $c$ mal $g$ ist.

Die Idee: Ab einer gewissen Eingabegröße wächst $f$ nicht schneller als ein konstantes Vielfaches von $g$ . Konstante Faktoren und Glieder niedrigerer Ordnung spielen dabei keine Rolle. Man schreibt oft ungenau $f = O(g)$ statt $f \in O(g)$ .

f \in O(g) \;:\Longleftrightarrow\; \exists\, c > 0,\ n_0:\ \forall n \ge n_0:\ f(n) \le c\cdot g(n)

Beispiel

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

Wir wählen $c = 4$ und $n_0 = 5$ . Für alle $n \ge 5$ gilt $5n \le n^2$ (denn $5 \le n$ ), also:

3n^2 + 5n \;\le\; 3n^2 + n^2 \;=\; 4n^2

Damit ist die Definition erfüllt. Ebenso gilt $100n + n^2 \in O(n^2)$ , denn für große $n$ dominiert das quadratische Glied. Umgekehrt ist $n^2 \notin O(n)$ : Egal wie groß $c$ ist, ab $n > c$ gilt $n^2 > c \cdot n$ .

Definition

Wichtige Wachstumsklassen

Diese Klassen begegnen dir in jedem Algorithmus-Lehrbuch, geordnet vom langsamsten zum schnellsten Wachstum:

$O(1)$ konstant: ein Arrayzugriff.
$O(\log n)$ logarithmisch: binäre Suche; jeder Schritt halbiert das Problem.
$O(n)$ linear: ein Durchlauf durch die Daten.
$O(n \log n)$ linearithmisch: gute Sortierverfahren wie Mergesort.
$O(n^2)$ quadratisch: zwei verschachtelte Schleifen, einfache Sortierverfahren.
$O(2^n)$ exponentiell: alle Teilmengen durchprobieren.

Mit dem Logarithmus ist in der Informatik fast immer der Logarithmus zur Basis $2$ gemeint. Die Basis ändert nur einen konstanten Faktor und ist in der O-Notation egal.

1 \;\prec\; \log n \;\prec\; n \;\prec\; n\log n \;\prec\; n^2 \;\prec\; 2^n

Was die Zahlen bedeuten. Nimm an, ein Rechner schafft $10^9$ einfache Operationen pro Sekunde. Bei $n = 10^6$ braucht ein $O(n \log n)$ -Verfahren etwa $20 \cdot 10^6$ Schritte, also Sekundenbruchteile. Ein $O(n^2)$ -Verfahren braucht $10^{12}$ Schritte, das sind rund $17$ Minuten. Ein $O(2^n)$ -Verfahren ist schon bei $n = 60$ unbrauchbar, selbst auf dem schnellsten Rechner.

Beste, mittlere und schlechteste Laufzeit. Dasselbe Verfahren kann je nach Eingabe unterschiedlich schnell sein. Meist wird der ungünstigste Fall (Worst Case) angegeben, weil er eine Garantie liefert. Mit den Sortieralgorithmen des gleichnamigen Werkzeugs kannst du das selbst ausprobieren: Dort siehst du die Anzahl der Vergleiche für sortierte, umgekehrt sortierte und zufällige Eingaben.

Zusammenfassung

Aufwand wird als Anzahl der Grundoperationen in Abhängigkeit von der Eingabegröße $n$ angegeben, nicht in Sekunden.
Die O-Notation ignoriert konstante Faktoren und Glieder niedrigerer Ordnung: $f \in O(g)$ , wenn $f(n) \le c\cdot g(n)$ ab einem $n_0$ .
Zwei verschachtelte Schleifen mit Dreiecksform liefern $\frac{n(n-1)}{2} \in O(n^2)$ .
Rangfolge: $1 \prec \log n \prec n \prec n\log n \prec n^2 \prec 2^n$ .
Meist wird die Worst-Case-Laufzeit angegeben, weil sie eine Garantie ist.

Übungen

Aufgabe 1Numerisch

Eine äußere Schleife läuft für $i = 0, \dots, n-1$ , die innere für $j = 0, \dots, i-1$ . Wie oft wird der Rumpf der inneren Schleife für $n = 10$ ausgeführt?

Aufgabe 2Multiple Choice

Welche der folgenden Aussagen ist richtig?

Aufgabe 3Numerisch

Ein Verfahren braucht ungefähr $n \cdot \log_2 n$ Schritte. Wie viele sind es für $n = 1024$ ?

Aufgabe 4Freitext

Zeige mit der Definition der O-Notation, dass $5n + 20 \in O(n)$ gilt. Gib $c$ und $n_0$ an.

Operationen in Schleifen zählen

Nachweis: 3n2+5n∈O(n2)3n^2 + 5n \in O(n^2)3n2+5n∈O(n2)

Zusammenfassung

Übungen

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