Randomizirani vs Rekurzivni algoritam
Randomizirani algoritmi uključuju logičnost u slučajnost odabirom tijekom izvršavanja 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 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, a mnogi programski jezici visoke razine podržavaju rekurziju.
Što je randomizirani algoritam?
Randomizirani algoritmi uključuju osjećaj slučajnosti donoseći nasumične izbore koji vode izvršenje algoritma. To se obično radi uzimajući kao dodatni ulaz skup slučajnih brojeva generiranih generatorom pseudosluč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 radno vrijeme O (n log n) bez obzira na ulazna svojstva. Nadalje, randomizirana inkrementalna metoda gradnje koristi se za građenje konstrukcija poput konveksnog trupa u proračunskoj geometriji. U ovoj se metodi ulazne točke nasumično permutiraju i zatim umetnu jedna po jedna u strukturu. Implementacija randomiziranog algoritma relativno je jednostavna od primjene determinističkog algoritma za isti problem. Najveći izazov u dizajniranju randomiziranog algoritma leži u izvođenju asimptotske analize složenosti vremena i prostora.
Što je rekurzivni algoritam?
Rekurzivni algoritmi temelje se na ideji da se rješenje problema može pronaći pronalaženjem rješenja manjih potproblema istog problema. U rekurzivnom algoritmu, funkcija je definirana u smislu ranije verzije same sebe. Važno je napomenuti da ovo samo referenciranje treba imati uvjet prekida kako bi se zauvijek izbjeglo samo referenciranje. Uvjet raskida provjerava se prije samog referenciranja. Početni korak rekurzivnog algoritma povezan je s 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že je prirodnom načinu razmišljanja od iterativnog algoritma za isti problem. Ali općenito,rekurzivni algoritmi zahtijevaju više memorije i računski su skupi.
Koja je razlika između slučajnog i rekurzivnog algoritma?
Slučajni 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 pronaći pronalaženjem rješenja za manje podprobleme istog problema. Zbog slučajnosti u slučajnim algoritmima, ponašanje algoritma moglo bi se promijeniti čak i za isti ulaz (u različitim izvedbama algoritma). Ali to nije moguće u rekurzivnim algoritmima, a ponašanje rekurzivnog algoritma bilo bi isto za fiksni ulaz.
