Naključni ali rekurzivni algoritem
Naključni algoritmi vključujejo občutek naključnosti v svojo logiko tako, da med izvajanjem algoritma sprejemajo naključne odločitve. Zaradi te naključnosti se lahko obnašanje algoritma spremeni tudi pri fiksnem vhodu. Za številne težave naključni algoritmi zagotavljajo najbolj preproste in učinkovite rešitve. Rekurzivni algoritmi temeljijo na ideji, da je rešitev problema mogoče najti z iskanjem rešitev za manjše podprobleme istega problema. Rekurzija se pogosto uporablja za iskanje rešitev za probleme v računalništvu in številni visokonivojski programski jeziki podpirajo rekurzijo.
Kaj je naključni algoritem?
Naključni algoritmi vključujejo občutek naključnosti z naključnimi izbirami, ki vodijo izvajanje algoritma. To se običajno naredi tako, da se kot dodatni vhod vzame nabor naključnih števil, ki jih ustvari generator psevdonaključnih števil. Zaradi tega se lahko obnašanje algoritma spremeni tudi pri fiksnem vnosu. Quicksort je splošno znan algoritem, ki uporablja koncept naključnosti in ima čas delovanja O(n log n) ne glede na vhodne lastnosti. Poleg tega se metoda naključne inkrementalne konstrukcije uporablja za gradnjo struktur, kot je konveksni trup v računalniški geometriji. Pri tej metodi so vhodne točke naključno permutirane in nato ena za drugo vstavljene v strukturo. Implementacija randomiziranega algoritma je razmeroma preprosta kot implementacija determinističnega algoritma za isti problem. Največji izziv pri oblikovanju randomiziranega algoritma je izvajanje asimptotične analize za kompleksnost časa in prostora.
Kaj je rekurzivni algoritem?
Rekurzivni algoritmi temeljijo na ideji, da je rešitev problema mogoče najti z iskanjem rešitev za manjše podprobleme istega problema. V rekurzivnem algoritmu je funkcija definirana v smislu prejšnje različice same sebe. Pomembno je opozoriti, da mora imeti to samosklicevanje pogoj za prekinitev, da se za vedno izognete sklicevanju samo na sebe. Prekinitveni pogoj se preveri pred samim sklicevanjem. Začetni korak rekurzivnega algoritma je povezan z osnovno klavzulo rekurzivne definicije problema. Koraki, ki sledijo začetnemu koraku, so povezani z induktivnimi stavki problema. Rekurzivni algoritmi nudijo preprostejšo rešitev v številnih situacijah in so bližje naravnemu načinu razmišljanja kot iterativni algoritem za isti problem. Toda na splošno rekurzivni algoritmi zahtevajo več pomnilnika in so računsko dragi.
Kakšna je razlika med randomiziranim in rekurzivnim algoritmom?
Naključni algoritmi so algoritmi, ki uporabljajo občutek naključnosti z naključnimi odločitvami, ki bi lahko vplivale na izvajanje algoritma, medtem ko so rekurzivni algoritmi algoritmi, ki temeljijo na ideji, da je rešitev problema mogoče najti z iskanjem rešitve za manjše podprobleme istega problema. Zaradi naključnosti v naključnih algoritmih se lahko obnašanje algoritma spremeni tudi pri istem vnosu (pri različnih izvedbah algoritma). Toda to ni mogoče v rekurzivnih algoritmih in vedenje rekurzivnega algoritma bi bilo enako za fiksni vnos.
