Рекурсивный Fibonacci с мемоизацией
Мемоизация сохраняет ранее вычисленные результаты.
Что такое Рекурсивный Fibonacci с мемоизацией?
Мемоизация сохраняет ранее вычисленные результаты.
Избегайте повторного вычисления одинаковых значений.
Когда это использовать?
- Понимать алгоритмы и структуры данных.
- Наблюдать каждый шаг и проверять граничные случаи.
- Сравнивать время работы и память.
Пример кода
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))Ожидаемый результат
55Как это работает
Кэш сокращает экспоненциальное время до O(n), используя O(n) памяти.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Практические задания
Изменяйте входные данные и проверяйте граничные случаи перед работой с большими наборами.
- Проверьте пустой ввод, один элемент и дубликаты.
- Выводите состояние после каждого шага.
- Сравните производительность с другим решением.