4.1 Определение мемоизации и её основные концепции
Мемоизация — это техника оптимизации, при которой результаты дорогостоящих функций сохраняются, чтобы их можно было повторно использовать при последующих вызовах с теми же аргументами. Это уменьшает количество повторных вычислений, тем самым увеличивая производительность.
Основные концепции:
1. Кэширование:
Сохранение результатов функции в некоторой структуре данных (например, в словаре или массиве), чтобы при повторном вызове с теми же аргументами вернуть уже сохранённый результат, а не вычислять его заново.
2. Таблица поиска (Lookup Table):
Структура данных, используемая для хранения результатов предыдущих вызовов функции. Это может быть хеш-таблица (словарь) или массив.
3. Рекурсивные вызовы:
Мемоизация особенно полезна для рекурсивных функций, где одни и те же подзадачи могут выполняться несколько раз с одинаковыми параметрами.
Временная и пространственная сложность оптимизированных алгоритмов:
Временная сложность:
Для многих рекурсивных задач мемоизация снижает временную сложность за счёт сокращения количества повторных вычислений. Например, рекурсивное вычисление чисел Фибоначчи имеет временную сложность O(2^n), а с мемоизацией — O(n).
Пространственная сложность:
Пространственная сложность увеличивается за счёт хранения результатов в кэше. Обычно это O(n) для задачи, требующей мемоизации.
Резюме:
Мемоизация — это мощная техника оптимизации рекурсивных алгоритмов, позволяющая значительно улучшить их производительность за счёт сокращения количества повторных вычислений.
Она особенно полезна для задач, в которых одни и те же подзадачи выполняются многократно с одинаковыми параметрами. Понимание концепций мемоизации и её применение на практике позволяет эффективно решать задачи с высоким вычислительным накладом.
4.2 Примеры оптимизации
Примеры оптимизации рекурсивных алгоритмов с использованием мемоизации
Пример 1: Числа Фибоначчи
Рекурсивный алгоритм вычисления чисел Фибоначчи без мемоизации имеет экспоненциальную временную сложность. Использование мемоизации значительно улучшает производительность.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Пример использования:
print(fibonacci(10)) # Вывод: 55
Важно! Обратите внимание, что мы используем memo=None в качестве значения по умолчанию, а затем создаём пустой словарь внутри функции, если memo не передан. Это позволяет избежать проблемы с изменяемым объектом в качестве значения по умолчанию.
Пример 2: Сумма подмножеств
Нужно определить, существует ли подмножество заданного множества, сумма элементов которого равна заданному значению.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# Пример использования:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Вывод: True
Мемоизация — это фактически кэширование результатов подзадач.
Например, число Фибоначчи F(10) == F(9) + F(8), но чтобы вычислить F(9), нужно вычислить F(8) и F(7). То есть F(8) мы должны вычислить дважды: как первое слагаемое для F(9) и как второе слагаемое для F(10). Чтобы не вычислять его дважды, нужно кэшировать его после первого вычисления.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ