Algoritmi i rastësishëm kundrejt rekurziv
Algoritmet e rastësishme përfshijnë një ndjenjë rastësie në logjikën e saj duke bërë zgjedhje të rastësishme gjatë ekzekutimit të algoritmit. Për shkak të kësaj rastësie, sjellja e algoritmit mund të ndryshojë edhe për një hyrje fikse. Për shumë probleme, algoritmet e rastësishme ofrojnë zgjidhjet më të thjeshta dhe më efikase. Algoritmet rekursive bazohen në idenë se zgjidhja e një problemi mund të gjendet duke gjetur zgjidhje për nënprobleme më të vogla të të njëjtit problem. Rekursioni përdoret gjerësisht për të gjetur zgjidhje për problemet në shkencën kompjuterike dhe shumë gjuhë programimi të nivelit të lartë mbështesin rekursionin.
Çfarë është një algoritëm i rastësishëm?
Algoritmet e rastësishme përfshijnë një ndjenjë rastësie duke bërë zgjedhje të rastësishme që udhëheqin ekzekutimin e algoritmit. Kjo zakonisht bëhet duke marrë një grup numrash të rastësishëm të gjeneruar nga një gjenerues numrash pseudorandom si një hyrje shtesë. Për shkak të kësaj, sjellja e algoritmit mund të ndryshojë edhe për një hyrje fikse. Quicksort është një algoritëm i njohur gjerësisht që përdor konceptin e rastësisë dhe ka një kohë ekzekutimi prej O(n log n) pavarësisht nga vetitë e hyrjes. Më tej, metoda e rastësishme e ndërtimit në rritje përdoret për ndërtimin e strukturave si byk konveks në gjeometrinë llogaritëse. Në këtë metodë, pikat hyrëse ndërrohen në mënyrë të rastësishme dhe më pas futen një nga një në strukturë. Zbatimi i një algoritmi të rastësishëm është relativisht i thjeshtë sesa zbatimi i një algoritmi determinist për të njëjtin problem. Sfida më e madhe në hartimin e një algoritmi të rastësishëm qëndron në kryerjen e analizave asimptotike për kompleksitetin e kohës dhe hapësirës.
Çfarë është një algoritëm rekurziv?
Algoritmet rekursive bazohen në idenë se zgjidhja e një problemi mund të gjendet duke gjetur zgjidhje për nënprobleme më të vogla të të njëjtit problem. Në një algoritëm rekurziv, një funksion përcaktohet në termat e versionit të mëparshëm të vetvetes. Është e rëndësishme të theksohet se kjo vetë-referencë duhet të ketë një kusht përfundimi për të shmangur referencën përgjithmonë. Kushti i përfundimit kontrollohet përpara se të referohet vetë. Hapi fillestar i një algoritmi rekurziv lidhet me klauzolën bazë të përkufizimit rekurziv të problemit. Hapat që pasojnë hapin fillestar lidhen me fjalitë induktive të problemit. Algoritmet rekursive ofrojnë një zgjidhje më të thjeshtë në shumë situata dhe është më afër mënyrës natyrale të të menduarit sesa algoritmi iterativ për të njëjtin problem. Por në përgjithësi, algoritmet rekurzive kërkojnë më shumë memorie dhe ato janë llogaritëse të shtrenjta.
Cili është ndryshimi midis një algoritmi të rastësishëm dhe një algoritmi rekurziv?
Algoritmet e rastësishme janë algoritme që përdorin një ndjenjë rastësie duke bërë zgjedhje të rastësishme që mund të ndikojnë në ekzekutimin e algoritmit, ndërsa algoritmet rekurzive janë algoritme që bazohen në idenë se një zgjidhje për një problem mund të gjendet duke gjetur zgjidhje për nënprobleme më të vogla të të njëjtit problem. Për shkak të rastësisë në algoritmet e rastësishme, sjellja e algoritmit mund të ndryshojë edhe për të njëjtën hyrje (në ekzekutime të ndryshme të algoritmit). Por kjo nuk është e mundur në algoritmet rekurzive dhe sjellja e një algoritmi rekurziv do të ishte e njëjtë për një hyrje fikse.
