Мемоизация — это метод оптимизации, который сохраняет результаты ресурсоёмких вызовов функций и возвращает сохранённый результат, когда встречаются те же входные данные.
Без мемоизации (Фибоначчи):
fib(5) вызывает fib(4) + fib(3)
fib(4) вызывает fib(3) + fib(2) — fib(3) вычисляется ПОВТОРНО!
Экспоненциальная временная сложность: O(2^n)
С мемоизацией:
Каждое значение вычисляется ТОЛЬКО ОДИН РАЗ и сохраняется
Последующие вызовы с теми же входными данными возвращают результат мгновенно
Линейная сложность: O(n) по времени, O(n) по памяти
Ключевая идея: обмен памяти на скорость
- Сохранять результаты в словаре или массиве
- Перед вычислением проверять, существует ли уже результат
- Значительное ускорение при наличии перекрывающихся подзадач
Похожие алгоритмы
Частые вопросы
- Что такое Мемоизация?
- Мемоизация — это метод оптимизации, который сохраняет результаты ресурсоёмких вызовов функций и возвращает сохранённый результат, когда встречаются те же входные данные.
- Какова сложность Мемоизация?
- Мемоизация объясняется с помощью пошаговой визуализации, включая временную и пространственную сложность.
- Для кого предназначена визуализация Мемоизация?
- Визуализация Мемоизация рассчитана на средний уровень в категории «Основы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Мемоизация?
- В той же категории (Основы) вы можете изучить: Big O Notation, Recursion, Two Pointers. Каждый из них имеет интерактивную визуализацию.