Laufzeit

Eine der wichtigsten Eigenschaften eines Algorithmus ist seine Laufzeit, das heißt, wie lange er benötigt, um seine Aufgabe zu erledigen.

Nun ist es natürlich offensichtlich, dass jeder Algorithmus eine kleine Eingabe schneller abarbeiten kann als eine große. Deswegen wird die Laufzeit eines Algorithmus immer in Abhängigkeit von der Länge seiner Eingabe angegeben.

Beispiel: Schriftlich rechnen

Schriftliche Addition

Eine schriftliche Addition

Nehmen wir an, wir berechnen schriftlich die Summe $652+471=1123$. Diese Berechnung besteht aus drei kleinen Einzelsummen: $2+1=3$, $5+7=12$ und $1+6+4=11$, wobei die 1 der Übertrag aus der letzten Addition ist. Jede dieser einzelnen Summen führen wir im Kopf durch, entscheidend ist die Anzahl der einzelnen Summen, die berechnet werden müssen. Um zwei dreistellige Zahlen zu addieren, muss man also drei einzelne Additionen durchführen.

Allgemein gesprochen: wenn man zwei Zahlen mit jeweils $n$ Ziffern addiert, muss man $n$ kleine Einzel-Additionen durchführen.

Das heißt: Wenn sich die Länge der Summanden verdoppelt, verdoppelt sich auch die Rechenzeit bei der schriftlichen Addition. Verzehnfacht sich die Länge der Summanden, verzehnfacht sich auch die Rechenzeit.

Schriftliche Multiplikation

Eine schriftliche Multiplikation

Nehmen wir an, wir berechnen schriftlich das Produkt $8642\cdot 9731=84095302$. Für diese Berechnung müssen vier einzelne Multiplikationen durchgeführt werden: $8642\cdot 9=77778$, $8642\cdot 7=60494$, $8642\cdot 3=25926$ und $8642\cdot 1=8642$, die dann versetzt aufeinander addiert werden. Jede dieser vier Multiplikationen besteht wiederum aus vier kleinen Multiplikationen aus dem Kleinen Einmaleins, sodass insgesamt sechzehn kleine Multiplikationen ausgeführt werden müssen.

Zum Schluss werden noch vier Additionen durchgeführt, bei denen eine insgesamt achtstellige Zahl herauskommt.

Allgemein gesprochen: wenn man zwei Zahlen mit jeweils $n$ Ziffern multipliziert, muss man $n^{2}$ kleine Einzel-Multiplikationen und $n\cdot 2n$ kleine Einzel-Additionen durchführen.

Das heißt: Wenn sich die Länge der Faktoren verdoppelt, vervierfacht sich die Rechenzeit bei der schriftlichen Addition. Verzehnfacht sich die Länge der Summanden, verhundertfacht sich die Rechenzeit.

𝒪-Notation

Die genauen Details, wie viele Schritte nun exakt nötig sind, sind eher unerheblich. Interessant ist nur, in welcher groben Größenordnung man unterwegs ist. Deswegen benutzt man in der Informatik die ${\mathcal {O}}$-Notation, um Laufzeiten zu beschreiben.

• ${\mathcal {O}}(n)$ bedeutet: zwischen der Länge der Eingabe und der Laufzeit besteht ein linearer Zusammenhang; wenn die Länge der Eingabe sich ver-$n$-facht, ver-$n$-facht sich auch die Laufzeit des Algorithmus.
• ${\mathcal {O}}(n^{2})$ bedeutet: zwischen der Länge der Eingabe und der Laufzeit besteht ein quadratischer Zusammenhang; wenn die Länge der Eingabe sich ver-$n$-facht, ver-$n^{2}$-facht sich die Laufzeit des Algorithmus.
• ${\mathcal {O}}(1)$ bedeutet: zwischen der Länge der Eingabe und der Laufzeit besteht kein Zusammenhang; wenn die Länge der Eingabe sich ver-$n$-facht, bleibt die Laufzeit des Algorithmus konstant.

Ganz allgemein gilt: Wenn ich sage: "Die Laufzeit vom Algorithmus X liegt in ${\mathcal {O}}(n^{3})$", dann meine ich: "Die Laufzeit lässt sich als mathematischer Term mit der Variablen $n$ angeben und es gibt eine Zahl $c$, sodass gilt: ab einer gewissen Schwelle ist der Term, der die Laufzeit beschreibt, kleiner als $c\cdot n^{3}$".

Grundsätzlich kann in die Klammern hinter dem ${\mathcal {O}}$ jeder beliebige mathematische Term geschrieben werden. Das Ziel der Notation ist es aber, die Größenordnung der Laufzeit schnell deutlich zu machen, weswegen man sich bemüht, den Term möglichst knapp, aber auch möglichst präzise zu halten.

Die ${\mathcal {O}}$-Notation gibt nämlich nur eine obere Schwelle an. ${\mathcal {O}}(n^{5})$ heißt nicht, dass sich die Laufzeit exakt in der Größenordnung von $n^{5}$ bewegt, sondern nur, dass sie nicht schneller wächst.

Weblinks

• "Laufzeitabschätzungen" auf inf-schule.de 🇩🇪
• "Asymptotisches Wachstumsverhältnis" auf inf-schule.de 🇩🇪