Мемоізація

4.1 Визначення мемоізації та її основні концепції.

Мемоізація — це техніка оптимізації, при якій результати дорогих функцій зберігаються, щоб їх можна було повторно використовувати при наступних викликах з тими ж аргументами. Це зменшує кількість повторних обчислень, тим самим збільшуючи продуктивність.

Основні концепції:

1. Кешування:

Збереження результатів функції в деякій структурі даних (наприклад, в словнику або масиві), щоб при повторному виклику з тими ж аргументами повернути вже збережений результат, а не обчислювати його наново.

2. Таблиця пошуку (Lookup Table):

Структура даних, що використовується для зберігання результатів попередніх викликів функції. Це може бути хеш-таблиця (словар) або масив.

3. Рекурсивні виклики:

Мемоізація особливо корисна для рекурсивних функцій, де одні й ті ж підзадачі можуть виконуватися кілька разів з однаковими параметрами.

Часова та просторово-складність оптимізованих алгоритмів:

Часова складність:

Для багатьох рекурсивних задач мемоізація знижує часову складність завдяки скороченню кількості повторних обчислень. Наприклад, рекурсивне обчислення чисел Фібоначчі має часову складність O(2^n), а з мемоізацією — O(n).

Просторова складність:

Просторова складність зростає завдяки зберіганню результатів у кеші. Зазвичай це O(n) для задачі, що вимагає мемоізації.

Резюме:

Мемоізація — це потужна техніка оптимізації рекурсивних алгоритмів, що дозволяє значно покращити їх продуктивність завдяки скороченню кількості повторних обчислень.

Вона особливо корисна для задач, в яких одні й ті ж підзадачі виконуються багаторазово з однаковими параметрами. Розуміння концепцій мемоізації та її застосування на практиці дозволяє ефективно розв'язувати задачі з високим обчислювальним навантаженням.

4.2 Приклади оптимізації.

Приклади оптимізації рекурсивних алгоритмів з використанням мемоізації

Приклад 1: Числа Фібоначчі

Рекурсивний алгоритм обчислення чисел Фібоначчі без мемоізації має експоненційну часову складність. Використання мемоізації значно покращує продуктивність.

def fibonacci(n, 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 створюється один раз і потім кожного разу при виклику функції посилання передається в змінну memo.

Приклад 2: Сума підмножин

Потрібно визначити, чи існує підмножина заданої множини, сума елементів якої дорівнює заданому значенню.

def is_subset_sum(arr, n, sum, memo={}):
    if (n, sum) in memo:
        return memo[(n, sum)]
    if sum == 0:
        return True
    if n == 0 and sum != 0:
        return False
    if arr[n - 1] > sum:
        memo[(n, sum)] = is_subset_sum(arr, n - 1, sum, memo)
        return memo[(n, sum)]
    memo[(n, sum)] = is_subset_sum(arr, n - 1, sum, memo) or is_subset_sum(arr, n - 1, sum-arr[n - 1], memo)
    return memo[(n, sum)]

# Приклад використання:
arr = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(arr)
print(is_subset_sum(arr, n, sum))  # Вивід: True

        

Мемоізація — це фактично кешування результатів підзадач.

Наприклад число Фібоначчі F(10) == F(9)+F(8), але щоб обчислити F(9) потрібно обчислити F(8) і F(7). Тобто F(8) ми повинні обчислити двічі: як перший доданок для F(9) і як другий доданок для F(10). Щоб не обчислювати його двічі, потрібно кешувати його після першого обчислення.

1

Опитування

Рекурсія, рівень 18, лекція 3

Недоступний

Рекурсія

Рекурсія

Відкрити