Randomizirani naspram rekurzivnog algoritma
Randomizirani algoritmi uključuju osjećaj slučajnosti u svoju logiku donošenjem slučajnih izbora tijekom izvršavanja algoritma. Zbog ove slučajnosti, ponašanje algoritma se može promijeniti čak i za fiksni ulaz. Za mnoge probleme nasumični algoritmi daju najjednostavnija i najučinkovitija rješenja. Rekurzivni algoritmi temelje se 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 računalnoj znanosti i mnogi programski jezici visoke razine podržavaju rekurziju.
Što je randomizirani algoritam?
Randomizirani algoritmi uključuju osjećaj slučajnosti donošenjem slučajnih izbora koji usmjeravaju izvršenje algoritma. To se obično radi uzimanjem skupa slučajnih brojeva koje generira generator pseudoslučajnih brojeva kao dodatnog ulaza. 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 izvođenja od O(n log n) bez obzira na ulazna svojstva. Nadalje, nasumična inkrementalna metoda konstrukcije koristi se za izgradnju struktura poput konveksnog trupa u računskoj geometriji. U ovoj metodi, ulazne točke se nasumično mijenjaju i zatim umeću 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 vremenske i prostorne složenosti.
Što je rekurzivni algoritam?
Rekurzivni algoritmi temelje se na ideji da se rješenje problema može pronaći pronalaženjem rješenja za manje podprobleme istog problema. U rekurzivnom algoritmu, funkcija je definirana u smislu svoje ranije verzije. Važno je napomenuti da ovo samoreferenciranje treba imati uvjet prekida kako bi se zauvijek izbjeglo samoreferenciranje. Uvjet raskida se provjerava prije samog referiranja. Početni korak rekurzivnog algoritma povezan je s baznom klauzulom rekurzivne definicije problema. Koraci koji slijede nakon početnog koraka povezani su s induktivnim rečenicama problema. Rekurzivni algoritmi daju jednostavnije rješenje u mnogim situacijama i bliži su prirodnom načinu razmišljanja od iterativnog algoritma za isti problem. Ali općenito, rekurzivni algoritmi zahtijevaju više memorije i računalno su skupi.
Koja je razlika između randomiziranog i rekurzivnog algoritma?
Slučajni algoritmi su algoritmi koji koriste osjećaj slučajnosti donošenjem slučajnih izbora koji bi mogli utjecati na izvršenje algoritma, dok su rekurzivni algoritmi algoritmi koji se temelje na ideji da se rješenje problema može pronaći pronalaženjem rješenja za manje podprobleme istog problema. Zbog slučajnosti u slučajnim 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 bilo bi isto za fiksni unos.
