Algorytmy i struktury danych · Junior · Pytanie 28 z 75
Dlaczego ta funkcja Fibonacciego jest wolna dla n = 40?
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}- ✓Poprawna odpowiedź: W kółko oblicza te same wartości od nowa
- 2Dodawanie dużych liczb w JS jest kosztowne
- 3Rekurencja w JavaScripcie jest zawsze wolniejsza niż pętle
Wyjaśnienie
fib(n - 1) i fib(n - 2) obie liczą od nowa te same mniejsze wartości, więc drzewo wywołań ma około 2ⁿ węzłów. Zapamiętywanie wyników (memoizacja) lub zwykła pętla dają O(n).