Bazat e algoritmeve JavaScript Pjesa 5: Kuptimi i programimit dinamik me teknikën e memoizimit
Programimi dinamik
Programimi dinamik është një teknikë optimizimi që mund të aplikohet në një algoritëm rekurziv që ka thirrje të përsëritura me të njëjtat hyrje. Ideja themelore këtu është, nëse kemi zgjidhur një problem për një hyrje të caktuar, atëherë e ruajmë rezultatin si referencë dhe përdorim këtë rezultat të ruajtur në vend që të rillogaritim të gjithë problemin përsëri për të njëjtën hyrje, duke kursyer kështu kohën e ekzekutimit.
Në artikullin e mëparshëm, pamë se si zgjidhja rekursive e Fibonaccit çon në kompleksitetin eksponencial të kohës. Në këtë artikull, ne do të optimizojmë të njëjtën zgjidhje rekursive Fibonacci me programim dinamik për të marrë një kompleksitet linear kohor. Ju mund t'i referoheni shembullit të artikullit të mëparshëm në lidhjen më poshtë.
"Pjesa 4: Algoritmet rekursive dhe kompleksitetet e tyre kohore O(n) vs O(2^n)"
Memoizimi
Këtu do të përdorim teknika e memoizimit e programimit dinamik për të optimizuar zgjidhjen rekursive të problemit Fibonacci. Memoizimi thjesht nënkupton ruajtjen e të dhënave në mënyrë që ato të mund të përdoren më vonë për të kryer një proces të caktuar.
Rekursioni, ne e dimë, është i shkëlqyeshëm për llogaritje të përsëritura, por siç e shohim në pemën e rekursionit më poshtë, ai mund të çojë në punë të dyfishtë në varësi të problemit që po zgjidhim. Degët e funksionit fib(2) në funksionin rekurziv të Fibonaccit ekzekutohen shumë herë. Ne po përsërisim të njëjtat llogaritje shumë herë, dhe kjo është pikërisht ajo që po shkakton problemin e normës eksponenciale të rritjes.
Pra, si do të na ndihmonte ruajtja e disa të dhënave?
Nëse e ruajmë rezultatin e fib(2) diku gjatë ekzekutimit të tij të parë, atëherë mund të kontrollojmë nëse kemi një rezultat për fib(2)në ekzekutimin e tij të dytë, dhe më pas ne nuk e bëjmë llogaritjen për herë të dytë. Në vend të kësaj, ne përdorim rezultatin e ruajtur për herë të dytë. Në këtë mënyrë ne mund të ruajmë thirrjen shtesë të funksionit të fib(2) herën tjetër, e cila nga ana tjetër na ruan thirrjet e mëtejshme në fib(1) dhe fib( 0) të cilat tashmë janë llogaritur si pjesë e fib(2).
Kjo është ideja, nëse mund të eliminojmë thirrjet shtesë të funksioneve, eliminojmë të gjitha degët e pemës rekursive. Dhe, kjo është ajo që ka të bëjë me programimin dinamik. Bëhet fjalë për rekursionin, zgjidhjen e një problemi të veçantë me memoizimin. Pra, duke ruajtur disa rezultate të ndërmjetme, ne mund të optimizojmë algoritmin rekurziv. Le të zbatojmë të njëjtën zgjidhje Fibonacci tani me memoizimin.
Zgjidhje me memoizim
Për të zbatuar memoizimin, do të na duhet ruajtje. Për shembullin tonë, ne do të përdornim një objektlokal që do të kalonte si argument në funksionin rekurziv. Fillimisht, ruajtja do të ishte bosh dhe ndërsa do të kryhet hapi më rekurziv, ai do të mbushet me rezultate të ndërmjetme.
Pra, çdo proces rekurziv merr ruajtjen e vet, i cili përdoret vetëm për atë pemë të veçantë rekursive.
function fib(n, storage) {
let result;
if(n === 0 || n === 1) {
result = 1;
} else {
result = fib(n - 1, storage) + fib (n - 2, storage)
}
return result;
}
fib(3, {}) // Passing empty object initially
Në funksionin e mësipërm, ne kemi prezantuar një argument të dytë që do t'i kalohet funksionit si një objekt për ruajtjen e rezultateve të ndërmjetme.
Por, funksioni është ende i paplotë pasi nuk po i ruajmë rezultatet e ndërmjetme.
Për ta bërë këtë, ne mund ta ruajmë rezultatin në objektin “storage” duke shtuar në mënyrë dinamike çelësin.
function fib(n, storage) {
let result;
if(n === 0 || n === 1) {
result = 1;
} else {
result = fib(n - 1, storage) + fib (n - 2, storage)
}
storage[n] = result; // Memoization
return result;
}
Meqenëse objekti "magazina" është një lloj referimi, vlera e tij do të vazhdojë përgjatë thirrjeve të funksionit dhe vetia që kemi shtuar në mënyrë dinamike do të jetë e disponueshme përgjatë thirrjeve të përgjithshme të funksionit. Edhe tani, ne ruajmë vetëm rezultatin e ndërmjetëm, por nuk po bëjmë asgjë me të.
Pra, ende, ne nuk kemi asnjë optimizim në vend. Prandaj, mungon një hap i fundit.
Ky hap do të ishte të kontrolloni nëse, për n, ne kemi tashmë një hyrje në objektin tonë “ruajtje”. Dhe, nëse kemi një rezultat të ruajtur në storage[n], atëherë e kthejmë rezultatin duke anashkaluar pjesën tjetër të kodit.
function fib(n, storage) {
let result;
if(storage[n]){ // Memoization
return storage[n]
}
if (n === 0 || n === 1) {
result = 1;
} else {
result = fib(n - 1, storage) + fib (n - 2, storage)
}
storage[n] = result; // Memoization
return result;
}
Me këtë optimizim, ne i kapërcejmë të gjithë hapat e mëtejshëm që mund të çojnë në më shumë thirrje funksionesh që çojnë në degë të përsëritura të thirrjeve të funksionit. Dhe, prandaj kemi shumë më pak ekzekutime funksionesh.
Siç mund ta shihni në pemën e mësipërme, dega dublikatë e fib(2)është anashkaluar plotësisht dhe përdor vlerën e ruajtur të funksionit fib(2) nga dega tjetër .
Cili është kompleksiteti i kohës sonë të re?
Është kompleksitet linear kohor. Sepse nëse ekzekutojmë algoritmin e mësipërm dhe bëjmë Analizën Asimptotike atëherë shohim që për një rritje në n marrim 2n përsëritje.
Pra, 2n tingëllon si kompleksiteti ynë i kohës dhe siç mësuam, ne thjesht e thjeshtojmë këtë në O(n) sepse ne kujdesemi për të përgjithshmen model. Kështu që ne shkuam nga O(2^n) në vetëm O(n), që është një përmirësim i madh. Kemi konvertuar një zgjidhje eksponenciale të kompleksitetit kohor në një zgjidhje kompleksiteti linear. Dhe arsyeja për këtë është që ne po i anashkalojmë të gjitha degët në pemë me këtë teknikë optimizimi, me ndihmën e programimit dinamik. Dhe, kjo teknikë është shumë e fuqishme kur bëhet fjalë për zgjidhjen e disa problemeve komplekse dhe të ndërlikuara.
Problemi i ngjitjes së shkallëve
Më poshtë është problemi i ngjitjes së shkallëve, i cili është një nga problemet e shkëlqyera për t'u zgjidhur duke përdorur metodën e programimit dinamik. Shumë probleme të ngjashme të PD janë pyetur gjatë intervistave të kodimit.
Deklarata e problemit
Po ngjitni një shkallë që kërkon n hapa për të arritur majën. Çdo herë që mund të ngjitni ose 1 ose 2 hapa në të njëjtën kohë. Duhet të numërojmë dhe të kthejmë numrin total të mënyrave unike për t'u ngjitur në majë të shkallëve.
Shembulli 1
Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top 1. 1 step + 1 step 2. 2 steps
Shembulli 2
Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
Ne mund ta zgjidhim këtë problem duke përdorur të njëjtën teknikë të memoizimit të diskutuar më sipër.
Shpresoj se e keni gjetur të dobishëm këtë artikull. Faleminderit per leximin.
Më shumë përmbajtje në PlainEnglish.io. Regjistrohu për buletinin tonë javor falas. Na ndiqni në Twitter, LinkedIn, YouTube, dhe Discord . Të interesuar në Growth Hacking? Shikoni Circuit.
