Алгоритми та структури даних · Junior · Запитання 28 з 75
Чому ця функція Фібоначчі повільна для n = 40?
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}- ✓Правильна відповідь: Вона знову й знову обчислює ті самі значення
- 2Додавати великі числа в JS дорого
- 3Рекурсія в JavaScript завжди повільніша за цикли
Пояснення
fib(n - 1) і fib(n - 2) обидва заново обчислюють ті самі менші значення, тож дерево викликів має близько 2ⁿ вузлів. Кешування результатів (мемоізація) чи простий цикл дають O(n).