Razlika između randomiziranog i rekurzivnog algoritma

Randomizirani vs rekurzivni algoritam

Randomizirani algoritmi uključuju osjećaj slučajnosti u svoju logiku donoseći nasumične odluke tijekom izvođenja algoritma. Zbog ove slučajnosti, ponašanje algoritma može se promijeniti čak i za fiksni ulaz. Za mnoge probleme randomizirani algoritmi pružaju najjednostavnija i najučinkovitija rješenja. Rekurzivni algoritmi temelje se na ideji da se rješenje problema može naći pronalaženjem rješenja za manje sub problema istog problema. Rekurzija se široko koristi za pronalaženje rješenja za probleme informatike, a mnogi programski jezici visoke razine podržavaju rekurziju.

Što je randomizirani algoritam?

Randomizirani algoritmi uključuju osjećaj slučajnosti donoseći slučajne izbore koji usmjeravaju izvršenje algoritma. To se obično radi tako što se kao dodatni ulaz uzme skup slučajnih brojeva koje generira generator pseudo slučajnih brojeva. 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 O (n log n) bez obzira na svojstva unosa. Nadalje, slučajna metoda inkrementalne konstrukcije koristi se za izgradnju građevina poput konveksnog trupa u geometriji proračuna. U ovoj se metodi ulazne točke nasumično permutiraju i ubacuju jedna po jedna u strukturu. Implementacija randomiziranog algoritma relativno je jednostavna od implementacije determinističkog algoritma za isti problem. Najveći izazov u dizajniranju randomiziranog algoritma leži u izvođenju asimptotske analize za složenost vremena i prostora.

Što je rekurzivni algoritam?

Rekurzivni algoritmi temelje se na ideji da se rješenje problema može naći pronalaženjem rješenja za manje sub problema istog problema. U rekurzivnom algoritmu funkcija se definira u odnosu na stariju verziju sebe. Važno je napomenuti da bi ovo samo referenciranje moralo imati uvjet prekida kako bi se izbjeglo referenciranje zauvijek. Uvjet prekida provjerava se prije upućivanja na sebe. Početni korak rekurzivnog algoritma povezan je s osnovnom klauzulom rekurzivne definicije problema. Koraci koji slijede nakon početnog koraka 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. No općenito, rekurzivni algoritmi zahtijevaju više memorije i računski su skupi.

Koja je razlika između randomiziranog i rekurzivnog algoritma?

Random algoritmi su algoritmi koji koriste osjećaj slučajnosti donoseći slučajne izbore 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 naći pronalaženjem rješenja za manje pod-probleme istog problema. Zbog slučajnosti u slučajnim algoritmima, ponašanje algoritma može se promijeniti čak i za isti ulaz (u različitim izvedbama algoritma). To kod rekurzivnih algoritama nije moguće, a ponašanje rekurzivnog algoritma bilo bi isto za fiksni ulaz.