Fachrat Informatik - Forum

Quoted

Original von Armin1906
Ich würde gerne wissen, wie man die Laufzeit eine rekursiven bzw. iterativen Prozedur berechnet und wie man den Proportionalitätsfaktor berechnen kann.

Eigentlich ganz einfach: Jede elementare Operation (z. B. ein Vergleich, eine Addition, eine Multiplikation) zählt als eine Zeiteinheit bei der Laufzeit. Wenn man sich nun noch überlegt, wie oft die Iteration/Rekursion durchgeführt wird, kommt man auf die Anzahl der Zeiteinheiten, die ingesamt (in Abhängigkeit von der Eingabe) benötigt werden.

Falls Du damit Probleme haben solltest, poste hier doch einfach mal ein Beispielprogramm und schreib auf, wie Du bei der Berechnung der Laufzeit vorgegangen bist und wo Du noch Probleme hast.

Achso: Eigentlich müßte man bei der Laufzeitberechnung noch berücksichtigen, daß beispielsweise Additionen von großen Zahlen länger dauern als Additionen von kleinen Zahlen. Das klammert man in der Regel aber von der Laufzeitberechnung aus, da derartige Einflußfaktoren nur selten ins Gewicht fallen. Was "elementare Operationen" sind, läßt sich also nicht pauschal sagen, hier kommt die Erfahrung ins Spiel.

In Scheme läuft das aber ein wenig anders ab. Dazu gab es ja die Übung.

In den passenden Quelltexten dafür findest du 2 Funktionen:
cputime und factor.

cputime ist quasi eine Stoppuhr. Mit der kannst du die Laufzeit eines Programmaufrufes messen. Das Ergebnis wird in Millisekunden zurückgegeben.


Mach ein paar Messungen, dann siehst du z.B. das bei doppelter Eingabemenge auch die doppelte Zeit (in etwa) herauskommt. Also schätzt du lineare Laufzeit:


Dann kannst du mit der factor-Funktion den Faktor bestimmen, um den das ideal ( (o n) ) von der realen abweicht: einfach die o-Funktion mit entsprechendem n und die reale Funktion mit gleich großem Eingabewert in die factor-Funktion stecken, und du bekommst heraus, um welchen Faktor es abweicht.


Wie man damit die Laufzeit für große Eingabemengen berechnen kann, ist in der Übung gezeigt worden.

Achja: das alles sind ja reale Laufzeitmessungen, also macht man am besten immer einen Mittelwert um Schwankungen auszugleichen.

cputime darfst du dafür verwenden, bzw. musst du sogar. Du findest diese beiden Prozeduren im Quelltext zu der entsprechenden Übung. Kopier sie einfach in deine Aufgabe rein.

Die unten angegebenen Befehle beziehen sich immer nur auf die selbst zu erstellenden Sachen.

Quoted

Original von oixio
In Scheme läuft das aber ein wenig anders ab. Dazu gab es ja die Übung.

In den passenden Quelltexten dafür findest du 2 Funktionen:
cputime und factor.

OK, also wieder das bekannte Problem: Fragen zu Übungsaufgaben stellen, aber die Aufgabenstellung nicht verraten oder zumindest verlinken ...

Die standen nichtmal im ersten Blatt, das sich mit dem Thema befasst hat, die waren implizit durch die Übung vorgegeben

Aber schön, dass du dich damit befasst (@OP) - mittlerweile scheint die verbreitete Taktik zu sein, auf die Punkte zu verzichten... seufz.