| Memoriseren verbetert dramatisch de efficiëntie van dynamische programmeeralgoritmen door redundante berekeningen te vermijden. Dynamisch programmeren lost problemen op door ze op te splitsen in kleinere, overlappende deelproblemen, waarbij elk deelprobleem slechts één keer wordt opgelost en de oplossingen ervan worden opgeslagen. Memoiseren is een top-down benadering om dit te bereiken.
Hier is hoe het werkt:
1. Recursieve structuur: Dynamische programmeerproblemen lenen zich vaak voor recursieve oplossingen. Een naïeve recursieve implementatie zou herhaaldelijk de oplossingen voor dezelfde deelproblemen berekenen, wat zou leiden tot exponentiële tijdscomplexiteit.
2. Resultaten opslaan: Memoiseren introduceert een datastructuur (meestal een hashtabel of array) om de oplossingen voor reeds berekende subproblemen op te slaan. Deze structuur wordt vaak een 'memo' of 'cache' genoemd.
3. De memo controleren: Voordat het algoritme een deelprobleem recursief oplost, controleert het eerst de memo. Als de oplossing al aanwezig is (wat betekent dat het deelprobleem al eerder is opgelost), wordt deze rechtstreeks uit de memo opgehaald, waardoor herberekening wordt vermeden.
4. Het resultaat opslaan: Als de oplossing niet in de memo wordt gevonden, lost het algoritme het subprobleem recursief op en *slaat* het resultaat vervolgens op in de memo voordat het wordt geretourneerd.
Voorbeeld:
Beschouw de berekening van de Fibonacci-reeks. Een naïeve recursieve benadering heeft een exponentiële complexiteit omdat veel Fibonacci-getallen meerdere keren worden herberekend. Met memorisatie:
```python
memo ={} # Initialiseer de memo
def fibonacci_memo(n):
als n in memo:
return memo[n] # Ophalen uit memo indien al berekend
als n <=1:
retour n
anders:
resultaat =fibonacci_memo(n-1) + fibonacci_memo(n-2)
memo[n] =resultaat # Bewaar het resultaat in de memo
resultaat terug
print(fibonacci_memo(5)) # Uitvoer:5
```
In dit voorbeeld slaat 'memo' de berekende Fibonacci-getallen op. Wanneer `fibonacci_memo(5)` wordt aangeroepen, roept het recursief `fibonacci_memo(4)` en `fibonacci_memo(3)` aan. `fibonacci_memo(3)` zal recursief `fibonacci_memo(2)` en `fibonacci_memo(1)` aanroepen. Echter, zodra `fibonacci_memo(1)` of `fibonacci_memo(2)` is berekend en opgeslagen in `memo`, zullen daaropvolgende oproepen van dezelfde subproblemen direct de opgeslagen resultaten retourneren, waardoor redundante berekeningen worden vermeden. Dit reduceert de tijdscomplexiteit van exponentieel naar lineair.
In wezen transformeert memoisatie een potentieel recursief algoritme met exponentiële tijd in een algoritme voor lineaire tijd (of polynomiale tijd in andere gevallen) door gebruik te maken van de kracht van het cachen van eerder berekende resultaten. Het is een krachtige optimalisatietechniek die vaak wordt gebruikt in combinatie met dynamisch programmeren om de efficiëntie te verbeteren. |
