Ratespiel

Komplexität

In der Informatik versteht man die Komplexität als die Anforderung eines Algorithmus an Computerressourcen. Hier werden hauptsächlich der Zeitaufwand und der Speicherbedarf betrachtet. Es gibt nun verschiedene Möglichkeiten den Verbrauch zu ermitteln. Hierzu wird eine Laufzeitanalyse des Algorithmus durchgeführt.

1. Ansatz: Direktes Messen der Laufzeit (z.B. in ms):

– Abhängig von vielen Parametern, wie Rechnerkonfiguration, Rechnerlast, Compiler, Betriebssystem, … – Deshalb: kaum übertragbar und ungenau

• 2. Ansatz: Zählen der benötigten Elementaroperationen des Algorithmus in Abhängigkeit von der Größe n der Eingabe

– Das algorithmische Verhalten wird als Funktion der benötigten Elementaroperationen dargestellt.

– Die Charakterisierung dieser elementaren Operationen ist abhängig von der jeweiligen Problemstellung und dem zugrunde liegenden Algorithmus.

– Beispiele für Elementaroperationen: Zuweisungen, Vergleiche, arithmetische Operationen, Zeigerdereferenzierungen oder Arrayzugriffe

Hierzu soll ein Spiel implementiert werden, welches das Zählen der Operationen verständlicher macht.