Memoisering förbättrar dramatiskt effektiviteten hos dynamiska programmeringsalgoritmer genom att undvika redundanta beräkningar. Dynamisk programmering löser problem genom att dela upp dem i mindre överlappande delproblem, lösa varje delproblem endast en gång och lagra sina lösningar. Memoisering är en top-down-strategi för att uppnå detta.
Så här fungerar det:
1. Rekursiv struktur: Dynamiska programmeringsproblem lånar sig ofta till rekursiva lösningar. En naiv rekursiv implementering skulle upprepade gånger beräkna lösningarna till samma delproblem, vilket leder till exponentiell tidskomplexitet.
2. lagringsresultat: Memoisering introducerar en datastruktur (vanligtvis en hashtabell eller array) för att lagra lösningarna på underproblem som redan har beräknats. Denna struktur kallas ofta ett "memo" eller "cache."
3. Kontrollera memo: Innan du rekursivt löser ett delproblem kontrollerar algoritmen först memo. Om lösningen redan finns (vilket betyder att delproblemet har lösts tidigare) hämtas den direkt från memo och undviker ersättning.
4. lagring av resultatet: Om lösningen inte finns i memo, löser algoritmen rekursivt underproblemet och lagrar * * resultatet i memo innan det returnerar det.
Exempel:
Tänk på Fibonacci -sekvensberäkningen. En naiv rekursiv metod har exponentiell komplexitet eftersom den beräknar många Fibonacci -nummer flera gånger. Med memoisering:
`` `python
memo ={} # initialisera memo
def fibonacci_memo (n):
Om n i memo:
returnera memo [n] # Hämta från memo om det redan är beräknat
Om n <=1:
returnera n
annan:
resultat =Fibonacci_memo (n-1) + Fibonacci_memo (n-2)
memo [n] =resultat # lagra resultatet i memo
avkastningsresultat
tryck (Fibonacci_Memo (5)) # Output:5
`` `
I det här exemplet lagrar "Memo" de beräknade Fibonacci -numren. När `fibonacci_memo (5)` kallas, kallar det rekursivt `Fibonacci_memo (4)` och `Fibonacci_memo (3) '. `Fibonacci_memo (3)` kommer att rekursivt ringa `fibonacci_memo (2)` och `fibonacci_memo (1)`. När `Fibonacci_memo (1)` eller `Fibonacci_Memo (2)` beräknas och lagras i 'memo', kommer efterföljande samtal till samma delproblem direkt att returnera de lagrade resultaten, och undvika redundant beräkning. Detta minskar tidskomplexiteten från exponentiell till linjär.
I huvudsak förvandlar memoisering en potentiellt exponentiell tids rekursiv algoritm till en linjär tid (eller polynom-tid i andra fall) algoritm genom att utnyttja kraften i caching tidigare beräknade resultat. Det är en kraftfull optimeringsteknik som ofta används i samband med dynamisk programmering för att förbättra effektiviteten.
