Randomizirani vs rekurzivni algoritam
Randomizirani algoritmi uključuju osjećaj slučajnosti u svoju logiku praveći nasumične izbore tokom izvršavanja algoritma. Zbog ove slučajnosti, ponašanje algoritma se može promijeniti čak i za fiksni ulaz. Za mnoge probleme, randomizirani algoritmi pružaju najjednostavnija i najefikasnija rješenja. Rekurzivni algoritmi se zasnivaju na ideji da se rješenje problema može pronaći pronalaženjem rješenja za manje podprobleme istog problema. Rekurzija se široko koristi za pronalaženje rješenja za probleme u kompjuterskoj nauci i mnogi programski jezici visokog nivoa podržavaju rekurziju.
Šta je nasumični algoritam?
Randomizirani algoritmi uključuju osjećaj slučajnosti donošenjem nasumičnih izbora koji usmjeravaju izvršenje algoritma. Ovo se obično radi uzimanjem skupa slučajnih brojeva koje generiše generator pseudoslučajnih brojeva kao dodatni ulaz. Zbog toga se ponašanje algoritma može promijeniti čak i za fiksni ulaz. Quicksort je široko poznat algoritam koji koristi koncept slučajnosti i ima vrijeme rada od O(n log n) bez obzira na svojstva ulaza. Nadalje, metod randomizirane inkrementalne konstrukcije se koristi za građevinske strukture poput konveksnog trupa u proračunskoj geometriji. U ovoj metodi, ulazne tačke se nasumično permutiraju i zatim ubacuju jedna po jedna u strukturu. Implementacija randomiziranog algoritma je relativno jednostavna od implementacije determinističkog algoritma za isti problem. Najveći izazov u dizajniranju randomiziranog algoritma leži u izvođenju asimptotske analize za vremensku i prostornu složenost.
Šta je rekurzivni algoritam?
Rekurzivni algoritmi su bazirani na ideji da se rješenje problema može naći pronalaženjem rješenja za manje podprobleme istog problema. U rekurzivnom algoritmu, funkcija je definirana u smislu prethodne verzije same sebe. Važno je napomenuti da ovo samoreferenciranje treba da ima uslov prekida kako bi se zauvijek izbjeglo referenciranje. Uslov prekida se provjerava prije samog referenciranja. Početni korak rekurzivnog algoritma povezan je sa osnovnom klauzulom rekurzivne definicije problema. Koraci koji slijede početni korak povezani su s induktivnim klauzulama problema. Rekurzivni algoritmi pružaju jednostavnije rješenje u mnogim situacijama i bliži su prirodnom načinu razmišljanja nego iterativni algoritam za isti problem. Ali generalno, rekurzivni algoritmi zahtijevaju više memorije i računski su skupi.
Koja je razlika između randomiziranog i rekurzivnog algoritma?
Slučajni algoritmi su algoritmi koji koriste osjećaj slučajnosti praveći nasumične izbore koji bi mogli utjecati na izvršenje algoritma, dok su rekurzivni algoritmi algoritmi koji se zasnivaju na ideji da se rješenje problema može pronaći pronalaženjem rješenja manjih podproblema istog problema. Zbog slučajnosti u nasumičnim algoritmima, ponašanje algoritma može se promijeniti čak i za isti ulaz (u različitim izvršavanjima algoritma). Ali to nije moguće u rekurzivnim algoritmima i ponašanje rekurzivnog algoritma bi bilo isto za fiksni ulaz.
