algorithm

Umschreibung schrittweiser, auf Regeln aufgebauter Problemlösung

Bücher zum Thema bei Amazon.de

Unter einem Algorithmus (engl. algorithm, der Name geht wahrscheinlich auf den persischen Mathematiker Abu Ja'far Muhammad ibn Musa Al-Khwarizmi, ca. 790-840, zurück) versteht man die Umschreibung der schrittweisen Lösung eines Problems mittels einer endlichen Anzahl von Regeln.

Im Alltag begegnet man Algorithmen z.B. in Kochrezepten oder Bedienungsanleitungen.

Sobald ein Algorithmus zur Lösung eines Problems steht, lässt sich diese mit Hilfe einer mathematischen Rechenmaschine realisieren.

Beim Programmieren wird ein Algorithmus meist in Pseudocode formuliert, der eine recht einfache Übersetzung in eine bestimmte Programmiersprache erlaubt.

Meist wird ein Algorithmus bei seiner Veröffentlichung bewertet, dies sagt aus, wie gut er ein bestimmtes Problem löst. Theoretisch gibt es zu jedem (lösbaren) Problem unendlich viele Algorithmen, die es lösen.

Zur Bewertung wird die sogenannte O-Notation verwendet. Dabei wird in Abhängigkeit der Problemgröße (z.B. die Anzahl der Datensätze, die verarbeitet werden müssen, meistens als n bezeichnet) die sehr ungefähre Anzahl der Schritte (entspricht in etwa der Zeit) angegeben. Diese Angabe dient nur der Größenzuordnung, damit nicht etwa durch einen doppelt so schnellen Prozessor die Bewertung ungültig wird.

Häufige Notationen (in aufsteigender Geschwindigkeit) sind:

• O(1) (unabhängig von der Problemgröße lässt sich das Problem in konstanter Zeit lösen),
  
  
• O(log n) (es muss nur ein Bruchteil der Daten zur Lösung verwendet werden, oft durch eine geeignete
Datenstruktur),


• O(n) (der Algorithmen muss alle Daten durchgehen - ob ein mal oder 50 mal ist irrelevant),
  
  
• O(n log n) (es muss für jeden Datensatz nur ein Bruchteil der Daten wiederum durchgegangen werden),
  
  
• O(n²) (für jeden Datensatz muss der gesamte Datenbestand durchgegangen werden).