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):

Im weiteren Verlauf wird dieser Punkt in der Aufgabe IKG/Rekursion bearbeitet

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

Dieser Ansatz soll mit Hilfe eines Spiels verdeutlicht werden.

Inhalt des Spiel ist es zu erraten welche Zahl zwischen 1 und 100 sich Spieler 1 gedacht hat. Verwendet folgenden Quellcode. Spieler 1 gibt eine Zahl ein und deckt dabei den Monitor ab. Spieler 2 muss raten. Ermittelt dabei, was wäre die geringste Anzahl an Versuchen, was die durchschnittliche Anzahl und die größte Anzahl an Versuchen. Welche Wertangabe hat einen Einfluss auf die Anzahl? Wie könnte eine mathematische Angabe der drei Werte lauten?

Wie könnte man das Spiel optimieren um ein besseres Laufzeitverhalten zu erreichen. Probiere es aus.