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.

Beispiele aus der Mathematik

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, wie zum Beispiel bei der Multiplikation $8642\cdot 9=77778$:

• $2\cdot 9=18$, 8 schreib hin, 1 im Sinn
• $4\cdot 9+1{\text{ im Sinn}}=37$, 7 schreib hin, 3 im Sinn
• $6\cdot 9+3{\text{ im Sinn}}=57$, 7 schreib hin, 5 im Sinn
• $8\cdot 9+5{\text{ im Sinn}}=77$, 77 schreib hin, weil danach nichts mehr kommt.

Insgesamt müssen also sechzehn kleine Multiplikationen ausgeführt werden. Zum Schluss werden noch vier Additionen durchgeführt, bei denen eine insgesamt achtstellige Zahl herauskommt. Jede Addition besteht dabei wieder aus acht einzelnen Additionen der Ziffern.

Für die Mulitplikation zweier $4$-stelliger Ziffern müssen also $4^{2}$ kleine Mulitiplikationen und $4\cdot (2\cdot 4)$ kleine Additionen ausgeführt werden.

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. Zwischen der Anzahl der Ziffern und der Anzahl der Rechenschritte besteht also ein quadratischer Zusammenhang.

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.

Teilbarkeit

Nehmen wir an, wir möchten bestimmen, ob eine Zahl $x$ durch 10 teilbar ist. Dafür betrachten wir die letzte Ziffer: ist sie eine 0, so ist $x$ durch 10 teilbar. Für diese Betrachtung ist es völlig unerheblich, ob die Zahl zwei, zwanzig oder zweihundert Ziffern hat. Die Laufzeit dieser Berechnung hängt nicht von der Länge der Eingabe ab.

Das heißt: Wenn sich die Länge der Zahl verdoppelt, bleibt die Laufzeit des Algorithmus konstant. Verzehnfacht sich die Länge der Zahl, bleibt die Laufzeit trotzdem konstant.

𝒪-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. Beispiele: Schriftliches Addieren, Suchen in einer unsortierten Liste.
• ${\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. Beispiele: Schriftliches Multiplizieren, Sortierverfahren wie Bubblesort.
• ${\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. Beispiel: Teilbarkeit durch 10, Pop beim Stack.

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 ab einer gewissen Schwelle der Term, der die Laufzeit beschreibt, kleiner ist 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 🇩🇪
• "Konzept Laufzeitkomplexität" auf oinf.ch 🇨🇭