Algorithmus – Eigenschaften und Laufzeit

Um die Frage mal schnell zu beantworten lässt sich ganz einfach sagen: ein Algorithmus ist eine genaue Bildungsvorschrift. Du kannst ihn mit einem Rezept oder eine Bauanleitung vergleichen, denn er ist nicht mehr als das. Besser gesagt sind sogar beides Algorithmen. Ganz so einfach lasse ich das aber nicht stehen. Es gibt natürlich noch viel mehr (genauere) Antworten auf die Frage: „Algorithmus- was ist das?“ und natürlich hat ein Algorithmus Eigenschaften die er erfüllen muss um als solcher bezeichnet zu werden. Zu diesen Eigenschaften gehört auch die Laufzeit, auf die ich weiter unten nochmal eingehe.

Definition Algorithmus

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. 

Quelle: Wikipedia, Beitrag: Algorithmus Link: https://de.m.wikipedia.org/wiki/Algorithmus

Ok, soweit so gut. Das ist aber definitiv nicht alles was sich dazu sagen lässt. Lass uns mal weiter ins Detail gehen.

Was macht eigentlich einen (guten) Algorithmus aus?

Eigenschaften eines Algorithmuses

Ein Algorithmus hat insgesamt vier wesentliche Eigenschaften, die ich dir anhand eines Beispiels versuche zu erklären.

Stellt euch vor ihr seid bei eurer Freundin zum Kaffee eingeladen und sie hat einen mega leckeren Kuchen gebacken. Nun fragst du sie nach dem Rezept, so dass du nächstes Mal den selben leckeren Kuchen backen kannst. Natürlich erwartest du, dass wenn du alle Schritte des Rezeptes genau so befolgst, du am Ende auch den selben Kuchen hast. Genau das ist die erste Eigenschaft von Algorithmen: die Determiniertheit. Das bedeutet nicht mehr, als das bei gleichen Startbedingungen und gleichen Verfahren, jedes mal das selbe Ergebnis raus kommt.

Um auch wirklich immer auf das selbe Ergebnis zu kommen muss jeder einzelne Schritt auch wirklich immer genau definiert sein, so dass es auch wirklich nur eine Möglichkeit gibt wie man den Algorithmus fortsetzen kann. Es wäre ziemlich ungünstig wenn in unseren Rezept stünde: „Nun vermengen Sie die Flüssigkeiten…“ anstelle von: „Nun vermengen Sie Eier und Milch…“.

Diese Eigenschaft nennen wir: Determinismus.

Egal wie lecker der Kuchen auch ist, aber irgendwann wollen wir natürlich auch mal fertig werden. Um zu gewährleisten, dass wir irgendwann fertig werden, muss der Algorithmus finit sein. Er muss also eine begrenzte/endliche Anzahl an Schritten haben.

Und da wir nun aber auch wirklich fertig werden wollen, muss unser Algorithmus auch das letzte Kriterium erfüllen: die Terminiertheit. Der Algorithmus läuft also für keine Eingabe in eine Endlosschleife und liefert früher oder später auch ein Ergebnis.

Zusammengefasst sind die Eigenschaften eines Algorithmuses:

• Determiniertheit
• Determinismus
• Finitheit
• Terminiertheit

Die Determiniertheit ist natürlich auch abhängig von seinem Nutzen.

Bei einem Laien musst du für eine Torte auch wirklich jeden einzelnen Schritt genau erklären. Du musst den Algorithmus in viel mehr Schritte unterteilen, so dass du am Ende auch auf das selbe Ergebnis kommst wie ein erfahrener Konditor. Im Vergleich dazu müsstest du bei dem Konditor nur noch definieren welche(r) Kuchen mit welcher Sahne/Creme… wann, wo hin muss. Du musst aber nicht genau erklären wie du diesen Kuchen machst .. oder diese Creme. Denn das weiß der Konditor ja (hoffentlich).

Definition Algorithmus durch seine Eigenschaften

Diese Definition ist auf Basis der Eigenschaften die ein Algorithmus erfüllen sollte.

Ein Algorithmus ist eine eindeutig definierte Handlungsvorschrift, bei der zu jedem Zeitpunkt der weitere Ablauf genau festgelegt ist und der in einer endlichen Anzahl von Schritten endet.

Effizienz und Laufzeit eines Algorithmuses

Wir können die Effizienz von Algorithmen bezüglich vieler unterschiedlicher Kriterien bewerten. Eines dieser Kriterien ist die Zeit die er benötigt um zu terminieren.

Die meisten Befehle benötigen so gut wie keine Zeit, daher sind sie für unsere Betrachtung auch nicht weiter relevant. Relevant sind für uns alle möglichen Zugriffe auf Daten( d.h. der Aufruf von Daten aus einem Array, einer Liste o.ä.) daher betrachten wir auch nur diese Aufrufe.

Landau-Notation und Zeitkomplexität

Wir betrachten damit die Gesamtheit der rechenaufwendigen Schritten die benötigt werden um zum Ziel zu kommen. Um anzugeben wie schnell ein Algorithmus tatsächlich ist verwenden wir die Landau-Notation oder auch O-Notation.

Hier wird angegeben wie viele Schritte notwenig sind um zum Ziel zu komme. Dabei überlegt man wie viele Schritte man im besten, durchschnittlichen und im schlechtesten Fall benötigt. Anschließend stellt sich noch die Frage, was davon in den meisten Fällen eintritt. Man kann so angeben, wie schnell der Algorithmus im Regelfall ist.

Die Angabe lautet dann folgendermaßen: O(Laufzeitklasse).

Laufzeitklassen

Die Laufzeitklassen tun genau das was ich dir eben erklärt habe: sie geben dir an mit wie vielen rechenaufwändigen Schritten der Algorithmus terminiert. Hier sind sämtliche Konstanten in dem Term irrelevant, da sie die Werte nicht der Art beeinflussen das es die Grundaussage des Termes verändert. Wenn man den Term \( n^2\) betrachtet hat er immer noch den selben Anstieg wie \( \frac{n^2}{2} \) und damit hat das „/2“ keinen nennenswerten Einfluss und kann ignoriert werden.

Jetzt fragst du dich natürlich zurecht welche Laufzeitklassen es denn gibt. Ich nenne dir jetzt hier die 6 relevantesten Laufzeitklassen. Dabei handelt es sich um:

• \(O(1), O(2),…\) 》 die konstante Laufzeit
• \(O(log n)\) 》 die logarithmische Laufzeit
• \(O(n)\) 》 die lineare Laufzeit
• \(O(n * log (n ))\) 》 die superlineare Laufzeit
• \(O(n^2)\) 》 die quadratische Laufzeit
• \(O(2^n) \) 》 die exponentielle Laufzeit

Hier kannst du sehen wie sich die Laufzeitklassen verhalten je nach Anzahl der Rechenschritte im Verhältniss zu der Zeit die sie benötigen um soviele Schritte zu lösen. Auf der x-Achse ist die Anzahl der Elementarschritte dargestellt und auf der y-Achse die dazugehörige Zeitdauer.

Just by the Way: Die Grafik habe ich mit GeoGebra erstellt, also solltest du mal etwas plotten müssen, weißt du wo du das gut online machen kannst. GeoGebra ist ein relativ mächtiges Tool.

---

Spickzettel

So, da du nun auch weißt was einen Algorithmus ausmacht, können wir anfangen und uns ein paar Algorithmen angucken. Bis dahin kannst du auch meine anderen Beiträge checken, da ist bestimmt noch was interessantes für dich dabei.

Wenn du auf dem Laufenden bleiben möchtest, abonniere doch einfach unseren Newsletter. Teilen und kommentieren ist natürlich auch gerne erwünscht.