31. Рефакторинг функции Фибоначчи #
Условие задачи:
🔥 Проведи рефакторинг функции вычисления числа Фибоначчи.
В оригинальном коде используется рекурсия без оптимизации, что приводит к экспоненциальной сложности.
Код:
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Спойлеры к решению
Подсказки
💡 Оригинальная сложность: Рекурсивное вычисление без мемоизации имеет экспоненциальную сложность O(2^n).
💡 Оптимизация: Используй итеративное вычисление или мемоизацию (динамическое программирование), чтобы снизить сложность до O(n).
💡 Итеративный подход: Применение цикла для последовательного вычисления чисел Фибоначчи – эффективное решение для данной задачи.
💡 Оптимизация: Используй итеративное вычисление или мемоизацию (динамическое программирование), чтобы снизить сложность до O(n).
💡 Итеративный подход: Применение цикла для последовательного вычисления чисел Фибоначчи – эффективное решение для данной задачи.
Решение
public class Fibonacci {
// Итеративная реализация с линейной сложностью O(n)
public static int fib(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int next = a + b;
a = b;
b = next;
}
return b;
}
public static void main(String[] args) {
System.out.println("fib(10) = " + fib(10)); // Пример: 55
}
}
📌 Что улучшилось?
✅ Снижение сложности: Итеративный подход снижает асимптотику с экспоненциальной до O(n).
✅ Экономия памяти: Использование двух переменных для хранения предыдущих значений вместо рекурсивного стека.
✅ Повышенная производительность: Новый подход позволяет эффективно вычислять Fibonacci для больших значений n.