Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| ef_informatik:sorting_csharp [2022-03-14 20:12] – sca | ef_informatik:sorting_csharp [2022-03-14 20:26] (aktuell) – sca | ||
|---|---|---|---|
| Zeile 769: | Zeile 769: | ||
| </ | </ | ||
| + | === Teil I === | ||
| + | |||
| + | Implementiere nun die rekursive Fibonacci Funktion dynamisch. Das heisst, die Zwischenresultate sollen in einer Liste oder einem Array gespeichert und wieder verwendet werden (Memoisation). Wie weit kannst du nun Folgenglieder der Fibonacci-Folge berechnen? | ||
| + | |||
| + | === Teil II === | ||
| + | |||
| + | Bestimme nun wieder, wie viele rekursive Funktionsaufrufe nötig sind. Vergleiche die dynamische mit der vorherigen, nicht dynamischen Implementierung. | ||
| + | |||
| + | <nodisp 2> | ||
| + | ++++Lösung| | ||
| + | Anzahl rekursive Funktionsaufrufe ist nun **linear** in $n$, genauer: $2n - 1$. Für $n=42$ sind es damit $83$ (dynamisch). Stellt man es den über 400 Millionen Funktionsaufrufe vom nicht dynamischen Code gegenüber, so sieht man, dass dies eine enorme Steigerung der Effizient ist! | ||
| + | ++++ | ||
| + | </ | ||
sca