4.1 Definicja memoizacji i jej podstawowe koncepcje
Memoizacja — to technika optymalizacji, w której wyniki kosztownych funkcji są przechowywane, aby mogły być ponownie wykorzystane przy kolejnych wywołaniach z tymi samymi argumentami. To zmniejsza liczbę ponownych obliczeń, tym samym zwiększając wydajność.
Podstawowe koncepcje:
1. Caching:
Przechowywanie wyników funkcji w jakiejś strukturze danych (na przykład w słowniku lub tablicy), aby przy kolejnych wywołaniach z tymi samymi argumentami zwrócić już zapisany wynik, zamiast go ponownie obliczać.
2. Tabela wyszukiwania (Lookup Table):
Struktura danych używana do przechowywania wyników wcześniejszych wywołań funkcji. Może to być hash table (słownik) lub tablica.
3. Wywołania rekurencyjne:
Memoizacja jest szczególnie użyteczna dla funkcji rekurencyjnych, gdzie te same podzadania mogą być wykonywane kilka razy z tymi samymi parametrami.
Złożoność czasowa i przestrzenna zoptymalizowanych algorytmów:
Złożoność czasowa:
Dla wielu rekurencyjnych zadań memoizacja zmniejsza złożoność czasową poprzez zmniejszenie liczby powtarzających się obliczeń. Na przykład, rekurencyjne obliczenie liczb Fibonacciego ma złożoność czasową O(2^n), a z memoizacją — O(n).
Złożoność przestrzenna:
Złożoność przestrzenna zwiększa się poprzez przechowywanie wyników w cache. Zwykle to O(n) dla zadania wymagającego memoizacji.
Podsumowanie:
Memoizacja — to potężna technika optymalizacji rekurencyjnych algorytmów, pozwalająca znacznie poprawić ich wydajność poprzez zmniejszenie liczby powtarzających się obliczeń.
Jest szczególnie użyteczna dla zadań, w których te same podzadania są wykonywane wielokrotnie z tymi samymi parametrami. Zrozumienie koncepcji memoizacji i jej zastosowanie w praktyce pozwala efektywnie rozwiązywać zadania z dużym obciążeniem obliczeniowym.
4.2 Przykłady optymalizacji
Przykłady optymalizacji rekurencyjnych algorytmów z użyciem memoizacji
Przykład 1: Liczby Fibonacciego
Rekurencyjny algorytm obliczania liczb Fibonacciego bez memoizacji ma wykładniczą złożoność czasową. Użycie memoizacji znacznie poprawia wydajność.
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]
# Przykład użycia:
print(fibonacci(10)) # Wynik: 55
Ważne! Zwróć uwagę, że używamy memo=None jako wartości domyślnej, a następnie tworzymy pusty słownik wewnątrz funkcji, jeśli memo nie jest przekazany. To pozwala uniknąć problemu z modyfikowalnym obiektem jako wartością domyślną.
Przykład 2: Suma podzbiorów
Trzeba określić, czy istnieje podzbiór danego zbioru, suma elementów którego jest równa danej wartości.
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)]
# Przykład użycia:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Wynik: True
Memoizacja — to w zasadzie caching wyników podzadań.
Na przykład, liczba Fibonacciego F(10) == F(9) + F(8), ale aby obliczyć F(9), musimy obliczyć F(8) i F(7). Czyli F(8) musielibyśmy obliczyć dwa razy: jako pierwsze składnik do F(9) i jako drugi składnik do F(10). Aby nie obliczać go dwa razy, musimy go zapisać po pierwszym obliczeniu.
GO TO FULL VERSION