Aufwandsbetrachtung
Den Rechen- und Verwaltungsaufwand analysieren
Wir betrachten die rekursive Funktionsdefinition aus dem letzten Abschnitt zusammen mit einem Funktionsaufruf.
anzahlWege : Int -> Int -> Int
anzahlWege n k =
if k == 0 || k == n then
1
else
anzahlWege (n - 1) (k - 1) + anzahlWege (n - 1) k
> anzahlWege 5 2
10 : number
Wie wird ein solcher Funktionsaufruf ausgewertet? Die folgende Übersicht verdeutlicht die einzelnen Berechnungsschritte, die Elm bei dem vorgegebenen Funktionsaufruf ausführt.
anzahlWege 5 2 -> anzahlWege 4 1 + anzahlWege 4 2 -> (anzahlWege 3 0 + anzahlWege 3 1) + anzahlWege 4 2 -> (1 + anzahlWege 3 1) + anzahlWege 4 2 -> (1 + (anzahlWege 2 0 + anzahlWege 2 1)) + anzahlWege 4 2 -> (1 + (1 + (anzahlWege 1 0 + anzahlWege 1 1))) + (anzahlWege 4 2) -> (1 + (1 + (1 + 1))) + (anzahlWege 4 2) -> ...
Aufgabe 1
- Erkläre die angegebenen Berechnungsschritte.
- Ergänze die noch fehlenden Berechnungsschritte.
- Begründe, warum das Berechnungsverfahren ineffizient ist.
- Finde durch Experimente heraus, für welche Zahlen die Funktion schnell genug ist und bei welchen Zahlen die Funktion sehr langsam wird.
Aufgabe 2 (für Experten)
Die Verarbeitungsschritte kann man mit der folgenden Funktion nachvollziehen. Erkläre wie das Ergebnis zustande kommt und wie es mit den oben gezeigten Berechnungsschritten zusammenhängt.
wege : Int -> Int -> String -> String
wege n k aufrufe =
let
aufrufeNeu =
aufrufe ++ "|" ++ String.fromInt n ++ String.fromInt k
in
if k == 0 || k == n then
aufrufeNeu
else
wege (n - 1) (k - 1) aufrufeNeu ++ wege (n - 1) k aufrufeNeu
> wege 5 2 ""
"|52|41|30|52|41|31|20|52|41|31|21|10|52|41|31|21|11|52|42|31|20|52|42|31|21|10|52|42|31|21|11|52|42|32|21|10|52|42|32|21|11|52|42|32|22" : String
