Algorithmen und Datenstrukturen · Junior · Frage 28 von 75
Warum ist diese Fibonacci-Funktion für n = 40 langsam?
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}- 1Sie berechnet dieselben Werte immer wieder neu
- 2Große Zahlen zu addieren ist in JS teuer
- 3Rekursion ist in JavaScript immer langsamer als Schleifen
Antwort zeigen
Richtige Antwort: Sie berechnet dieselben Werte immer wieder neu
Erklärung
fib(n - 1) und fib(n - 2) berechnen beide dieselben kleineren Werte neu, der Aufrufbaum hat also etwa 2ⁿ Knoten. Ergebnisse zu cachen (Memoisierung) oder eine einfache Schleife macht es O(n).