MISSION 03 · Laufzeit statt Ergebniswert

Eine Treppe, kein Feuerwerk.

Dein erster Zug: Entscheide, wie viele rekursive Aufrufe fun(x) pro Ebene startet.

03 / 17

Originalkern

Berechne die Laufzeit, stelle eine Rekurrenzrelation auf und löse sie in eine geschlossene Form.

Vorbedingung: Das Programm terminiert nur für x ≥ 1.

int fun(int x) {
  if (x == 1) return 1;
  int zw = fun(x - 1);
  return zw * x;
}

30-SEKUNDEN-START

Was passiert in einem Aufruf?

int zw = fun(x - 1) heißt: „Rufe dieselbe Funktion mit einem um 1 kleineren Problem auf und merke das Ergebnis.“

Baue die Rekurrenz

Eine Ebene erledigt konstant viel Arbeit und reicht dann an x−1 weiter. Welche Formel beschreibt das?

Wähle eine Rekurrenzrelation
Zähle im Code nur, wie oft fun(…) in einem nicht-trivialen Aufruf vorkommt.
Die Multiplikation zw * x kostet einen Schritt. Sie vervielfacht den Wert, nicht die Zahl der Aufrufe.

Kurble die Maschine

Die PDF zählt pro normalem Aufruf 3 Schritte, im Basisfall 2. Erzeuge die Werte nacheinander.

T(1) = 2

Prüfungssatz fertigstellen

Schreibe die geschlossene Form und die asymptotische Laufzeit. Beispielsyntax: 3x-1, Theta(x).

Wie fühlt sich genau diese Mechanik an?