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.

Schriftliche Multiplikation

🕳

Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:

O-Notation, mehr Beispiele

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.