Razlika med randomiziranim in rekurzivnim algoritmom

Naključni in rekurzivni algoritem

Randomizirani algoritmi vključujejo občutek naključnosti v svojo logiko tako, da med izvajanjem algoritma naključno izbirajo. Zaradi te naključnosti se lahko vedenje algoritma spremeni tudi za fiksni vhod. Za številne težave randomizirani algoritmi ponujajo najbolj enostavne 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 težav v računalništvu in mnogi programski jeziki na visoki ravni podpirajo rekurzijo.

Kaj je randomizirani algoritem?

Randomizirani algoritmi vključujejo občutek naključnosti, tako da naključno izbirajo, ki vodijo izvedbo algoritma. Običajno se to izvede tako, da se za dodaten vhod vzame niz naključnih števil, ki jih ustvari generator psevdo naključnih števil. Zaradi tega se lahko vedenje algoritma spremeni tudi pri fiksnem vhodu. Quicksort je splošno znan algoritem, ki uporablja koncept naključnosti in ima čas delovanja O (n log n) ne glede na vhodne lastnosti. Nadalje se za gradbene konstrukcije, kot je konveksni trup v računski geometriji, uporablja randomizirana inkrementalna konstrukcijska metoda. Pri tej metodi so vhodne točke naključno permutirane in nato ena za drugo vstavljene v strukturo. Izvedba randomiziranega algoritma je sorazmerno preprosta kot implementacija determinističnega algoritma za isto težavo. Največji izziv pri načrtovanju randomiziranega algoritma je izvajanje asimptotske analize za časovno in prostorsko kompleksnost.

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 glede na prejšnjo različico same. Pomembno je opozoriti, da bi moralo imeti to samooskrbovanje prenehanje, da se ne bi za vedno sklicevali. Pogoj prekinitve se preveri, preden se sklicuje nanj. Začetni korak rekurzivnega algoritma je povezan z osnovno klavzulo rekurzivne definicije problema. Koraki, ki sledijo začetnemu koraku, so povezani z induktivnimi klavzulami problema. Rekurzivni algoritmi ponujajo enostavnejšo rešitev v številnih situacijah in so za isti problem bližje naravnemu načinu razmišljanja kot iterativni algoritem. Toda na splošno rekurzivni algoritmi zahtevajo več pomnilnika in so računsko dragi.

Kakšna je razlika med naključnim 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, rekurzivni algoritmi pa so algoritmi, ki temeljijo na ideji, da je mogoče najti rešitev problema z iskanjem rešitev za manjše podprobleme iste težave. Zaradi naključnosti v naključnih algoritmih se lahko vedenje algoritma spremeni tudi za isti vhod (pri različnih izvedbah algoritma). Toda v rekurzivnih algoritmih to ni mogoče in obnašanje rekurzivnega algoritma bi bilo enako za fiksni vhod.