4.1 Definition der Memoisierung und ihre Hauptkonzepte
Memoisierung ist eine Optimierungstechnik, bei der die Ergebnisse kostenintensiver Funktionen gespeichert werden, um sie bei späteren Aufrufen mit den gleichen Argumenten wiederzuverwenden. Dies reduziert die Anzahl der erneuten Berechnungen und erhöht somit die Leistung.
Hauptkonzepte:
1. Caching:
Speichern der Ergebnisse einer Funktion in einer Datenstruktur (z.B. in einem Dictionary oder Array), um beim erneuten Aufruf mit den gleichen Argumenten das bereits gespeicherte Ergebnis zurückzugeben, anstatt es neu zu berechnen.
2. Lookup-Tabelle:
Eine Datenstruktur, die dazu verwendet wird, die Ergebnisse früherer Funktionsaufrufe zu speichern. Dies kann eine Hash-Tabelle (Dictionary) oder ein Array sein.
3. Rekursive Aufrufe:
Memoisierung ist besonders nützlich für rekursive Funktionen, bei denen dieselben Teilaufgaben mehrmals mit den gleichen Parametern ausgeführt werden können.
Zeit- und Raumkomplexität von optimierten Algorithmen:
Zeitkomplexität:
Für viele rekursive Probleme reduziert die Memoisierung die Zeitkomplexität durch
Verminderung der Anzahl der erneuten Berechnungen. Zum Beispiel hat die rekursive Berechnung
von Fibonacci-Zahlen eine Zeitkomplexität von O(2^n), mit Memoisierung jedoch O(n).
Raumkomplexität:
Die Raumkomplexität nimmt aufgrund der Speicherung der Ergebnisse im Cache zu. Normalerweise beträgt sie O(n) für ein Problem, das eine Memoisierung erfordert.
Zusammenfassung:
Memoisierung ist eine mächtige Technik zur Optimierung rekursiver Algorithmen, die die Leistung erheblich verbessern kann, indem sie die Anzahl der erneuten Berechnungen reduziert.
Sie ist besonders nützlich für Probleme, bei denen dieselben Teilaufgaben mehrfach mit den gleichen Parametern ausgeführt werden. Das Verständnis der Konzepte der Memoisierung und ihre Anwendung in der Praxis ermöglicht
es, Probleme mit hohem Rechenaufwand effizient zu lösen.
4.2 Beispiele für Optimierung
Beispiele für die Optimierung rekursiver Algorithmen mit Memoisierung
Beispiel 1: Fibonacci-Zahlen
Der rekursive Algorithmus zur Berechnung von Fibonacci-Zahlen ohne Memoisierung hat exponentielle Zeitkomplexität. Die Verwendung von Memoisierung verbessert die Leistung erheblich.
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]
# Beispiel für die Nutzung:
print(fibonacci(10)) # Ausgabe: 55
Wichtig! Beachte, dass wir
memo=None als Standardwert verwenden und dann ein
leeres Dictionary innerhalb der Funktion erstellen, wenn memo nicht übergeben wird. Dies
vermeidet das Problem eines veränderbaren Objekts als Standardwert.
Beispiel 2: Teilmengensumme
Es soll bestimmt werden, ob es eine Teilmenge eines gegebenen Sets gibt, deren Summe einem vorgegebenen Wert entspricht.
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)]
# Beispiel für die Nutzung:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # Ausgabe: True
Memoisierung ist im Grunde das Caching von Ergebnissen von Teilaufgaben.
Zum Beispiel Fibonacci-Zahl F(10) == F(9) + F(8), aber um
F(9) zu berechnen, muss F(8) und
F(7) berechnet werden. Das heißt, F(8) müssen wir zweimal berechnen: als erster
Summand für F(9) und als zweiter Summand für F(10). Um es nicht zweimal zu berechnen,
sollte es nach der ersten Berechnung zwischengespeichert werden.
GO TO FULL VERSION