Komplexität und Skalierbarkeit

Komplexität von Algorithmen

Ein Algorithmus hat eine hohe Speicherkomplexität, wenn er für seine Ausführung viel Speicherplatz benötigt. Ein Algorithmus hat eine hohe Rechenkomplexität, wenn er für seine Ausführung viel Rechenzeit benötigt. Algorithmen werden folgendermassen nach der Rechenkomplexität klassifiziert, wobei n für die Anzahl der Eingaben steht:

Abb. 12: Typische Ordnungen von Algorithmen

Konstante Algorithmen: Komplexität hängt nicht von n ab.

Lineare Algorithmen: Die Komplexität nimmt proportional zu n zu.

Polynomiale Algorithmen: Die Komplexität steigt quadratisch zu n.

Exponentielle Algorithmen: Die Komplexität steigt massiv schneller als n.

Skalierbarkeit

In der Informatik und Softwaretechnik bezeichnet Skalierbarkeit das Verhalten von Programmen oder Algorithmen bezüglich des Ressourcenbedarfs bei wachsenden Eingabemengen, also die Performance und die Komplexität: Ein Software-Produkt skaliert "gut", wenn es beispielsweise bei der zehnfachen Leistung (Nennlast) mit ca. den zehnfachen Ressourcen auskommt. Ein "schlecht" skalierendes Produkt hingegen würde bei doppelter Last bereits die zehnfachen Ressourcen benötigen und bei zehnfacher Last komplett ausfallen. (WIKIPEDIA)

Ein Beispiel für einen Algorithmus, dessen Komplexität massiv schneller zunimmt als die Anzahl der Eingaben und somit schlecht skaliert, ist das "TurtlePuzzle":

Die Aufgabe des Algorithmus ist es dabei, die Puzzle-Teile so anzuordnen, dass vier korrekte Schildkröten dargestellt werden. Die einzige Möglichkeit dazu ist, alle Möglichkeiten durchzuprobieren.

Während das erste Puzzle (mit n=4) in zehn Schritten gelöst wird, benötigt das zweite (mit n=9) 24862 Schritte. Beim Abspielen empfiehlt es sich, die Geschwindigkeit zu erhöhen und das Puzzle automatisch ablaufen zu lassen (siehe Bild)

Turtle-Puzzle mit n=4, sprich 4 Puzzle-Teilen

Turtle-Puzzle mit n=9, also 9 Puzzle-Teilen