Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Memoizácia:
* prístup: Zhora nadol (rekurzívny s ukladaním do vyrovnávacej pamäte). Začína sa pôvodným problémom a rekurzívne ho rozdeľuje na menšie podprava. Pretože sa vyrieši každý subproblem, jeho výsledok sa ukladá (uložené v vyrovnávacej pamäti) v dátovej štruktúre (zvyčajne v slovníku alebo tabuľke). Ak sa opäť stretne rovnaký podprokľovač, výsledok uloženia v pamäti sa vyberie namiesto toho, aby bol prepracovaný.
* implementácia: Typicky implementované pomocou rekurzívnych funkcií a vyrovnávacej pamäte. Vyrovnávacia pamäť sa zvyčajne implicitne riadi rekurzívnymi hovormi.
* Problémová vhodnosť: Vhodný pre problémy, kde nie je potrebné vyriešiť všetky subproblémy. Vypočítava a ukladá výsledky podpísaných problémov, ktoré sú skutočne potrebné na vyriešenie hlavného problému.
* Poradie vykonávania: Poradie riešenia podpísanov je určené rekurziou, prirodzene po štruktúre problému.
* Vplyv efektívnosti:
* * Performance Boost:* Výrazne zlepšuje výkon, keď sa algoritmus počas rekurzie stretne s rovnakými podskupinou viackrát. V mnohých prípadoch znižuje exponenciálnu časovú zložitosť na polynomický čas.
* * Riadenie:* vznikajú nejaké režijné náklady kvôli vyhľadávaniu nad hlavou a vyhľadávaním vyrovnávacej pamäte. Táto réžia môže byť niekedy významná pre menšie problémy, keď sú náklady na výpočet už nízke.
* * Zložitosť priestoru:* využíva priestor pre vyrovnávaciu pamäť, ktorá ukladá výsledky vyriešených podpísanov. Požadovaný priestor závisí od počtu jedinečných podskupín, ktoré sú skutočne vyriešené.
* Čítateľnosť: Môže byť intuitívnejšia a ľahšie implementovať ako dynamické programovanie, najmä ak je rekurzívna štruktúra problému jasná.
Dynamické programovanie:
* prístup: Zdola nahor (iteratívne s tabuľkou). Vyrieši všetky možné podskupiny v konkrétnom poradí, zvyčajne začínajúc najmenšími podprava a budujú sa k väčším. Výsledky všetkých podskupín sú uložené v tabuľke (často viacrozmerné pole).
* implementácia: Typicky implementované pomocou iteračných slučiek a tabuľky. Poradie výpočtu je výslovne riadené slučkami.
* Problémová vhodnosť: Najlepšie sa hodí pre problémy, keď sa musia vyriešiť všetky podprava, aby sa dosiahli konečné riešenie.
* Poradie vykonávania: Poradie, v ktorom sa vyriešia podpätie, je výslovne definované algoritmom, zvyčajne na základe závislostí medzi podpätňami.
* Vplyv efektívnosti:
* * Zvýšenie výkonu:* výrazne zlepšuje výkon vyhýbaním sa nadbytočným výpočtom. V mnohých prípadoch znižuje exponenciálnu časovú zložitosť na polynomický čas. Pretože používa iteračné slučky, všeobecne sa vyhýba režijnej nákladnej hodnote volaní, vďaka čomu je potenciálne rýchlejšia ako memoizácia.
* * Riadenie:* Využíva priestor pre tabuľku, ktorý ukladá výsledky * všetkých * možných podpísanov, dokonca aj tie, ktoré sa nemusia priamo použiť na vyriešenie hlavného problému.
* * Zložitosť priestoru:* využíva priestor pre tabuľku, ktorý ukladá výsledky všetkých možných podskupín. Môže to byť vyššie ako memoizácia, ak nie sú potrebné niektoré podprava.
* Čítateľnosť: Môže byť menej intuitívne ako memoizácia, najmä pri zložitých problémoch. Vyžaduje si starostlivé plánovanie na určenie správneho poradia riešenia subproblémov.
Kľúčové rozdiely sú zhrnuté:
| Funkcia | Memoizácia Dynamické programovanie
| ---------------- | ------------------------------------------------ | ------------------------------------------------- |
| Prístup | Zhora nadol (rekurzívny) Zdola nahor (iteratívne)
| Implementácia Rekurzívne funkcie + vyrovnávacia pamäť | Iteratívne slučky + tabuľka |
| Problémová vhodnosť Nie všetky subproblémy môžu byť potrebné vyriešiť Všetky subproblémy je potrebné vyriešiť
| Poradie vykonávania Určené rekurziou Výslovne definované (často iteratívne)
| Využitie priestoru Ukladá výsledky * vyriešené * subproblémy | Ukladá výsledky * všetkých možných * subproblémov |
| Režijné náklady Funkcia hovoru nad hlavou, vyhľadávanie vyrovnávacej pamäte Menej režijných nákladov (žiadne volania funkcií)
| Čítateľnosť Často intuitívnejšie Môže byť menej intuitívny
Vplyv na efektívnosť (výkon):
* Čas zložitosť: Memoizácia aj dynamické programovanie môže drasticky znížiť časovú zložitosť algoritmov zahŕňajúcich prekrývajúce sa subproblémy, často od exponenciálnych (napr. O (2^n)) po polynóm (napr. O (n^2), o (n)).
* Vesmírna zložitosť: Obe techniky zvyšujú priestorovú zložitosť. Memoizácia ukladá výsledky vyriešených podskupín, zatiaľ čo dynamické programovanie ukladá výsledky všetkých možných podskupín. Výber medzi nimi môže závisieť od obmedzení pamäte a konkrétneho problému.
* Praktický výkon:
* V mnohých prípadoch môže byť dynamické programovanie o niečo rýchlejšie v dôsledku nižšej režijnej iteračnej slučky v porovnaní s rekurzívnymi funkčnými hovormi.
* Ak je však potrebné vyriešiť iba malú časť možných subproblémov, memoizácia môže byť efektívnejšia z hľadiska času aj priestoru, pretože počíta a ukladá potrebné výsledky.
Kedy použiť ktoré:
* Použite memoizáciu:
* Ak má problém prirodzenú rekurzívnu formuláciu.
* Ak nie je potrebné vyriešiť všetky subproblémy.
* Ak sú uprednostňované čitateľnosť a ľahká implementácia.
* Použite dynamické programovanie:
* Keď je potrebné vyriešiť všetky podprava, aby sa získalo konečné riešenie.
* Ak je výkon kritický a funkčné hovory by sa mali minimalizovať.
* Keď je prístup zdola nahor prirodzenejší pre problém.
Príklad (Fibonacci Sekvencia):
Memoizácia (python):
`` `Python
def fib_memo (n, memo ={}):
Ak n v memore:
návrat poznámky [n]
ak n <=1:
návrat n
memo [n] =fib_memo (n - 1, memo) + fib_memo (n - 2, memo)
návrat poznámky [n]
Print (Fib_memo (10)) # výstup:55
`` `
Dynamické programovanie (Python):
`` `Python
def fib_dp (n):
fib_table =[0] * (n + 1)
ak n> =0:
fib_table [0] =0
ak n> =1:
fib_table [1] =1
pre i v rozsahu (2, n + 1):
fib_table [i] =fib_table [i - 1] + fib_table [i - 2]
návrat fib_table [n]
tlač (fib_dp (10)) # výstup:55
`` `
V tomto príklade transformuje memoizácia aj dynamické programovanie naivné rekurzívne riešenie (ktoré má exponenciálnu časovú zložitosť) na algoritmus s časovou zložitosťou O (N). Dynamická programovacia verzia sa však vyhýba režijnému volaniu volania a v praxi bude spravidla o niečo rýchlejšia.