Naključni in rekurzivni algoritem
Naključni algoritmi v svojo logiko vključujejo občutek naključnosti z naključnimi izbirami med izvajanjem algoritma. Zaradi te naključnosti se lahko vedenje algoritma spremeni tudi za fiksni vhod. Za številne težave naključni algoritmi ponujajo 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 v računalništvu in številni programski jeziki na visoki ravni podpirajo rekurzijo.
Kaj je naključni algoritem?
Naključni algoritmi vključujejo občutek naključnosti z naključnimi odločitvami, ki vodijo izvedbo algoritma. To se običajno opravi tako, da se za dodaten vhod vzame niz naključnih števil, ki jih ustvari generator psevdonaključ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 randomizirana inkrementalna konstrukcijska metoda uporablja za gradbene konstrukcije, kot je konveksni trup, v računski geometriji. Pri tej metodi se vhodne točke naključno permutirajo in nato eno za drugo vstavijo v strukturo. Izvajanje naključnega algoritma je sorazmerno preprosto kot izvajanje determinističnega algoritma za isti problem. Največji izziv pri načrtovanju randomiziranega algoritma je izvajanje asimptotske analize časovne in prostorske zapletenosti.
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 omeniti, da mora imeti to samonavajanje referenčni pogoj, da se za vedno izogne sklicevanju. Preklicni pogoj se preveri, preden se sklicuje sam. 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 ponujajo preprostejšo rešitev v mnogih situacijah in je bližje naravnemu načinu razmišljanja kot iterativni algoritem za isti problem. Toda na splošnorekurzivni 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, medtem ko so rekurzivni algoritmi algoritmi, ki temeljijo na ideji, da je rešitev problema mogoče najti z iskanjem rešitev za manjše podprobleme. istega problema. Zaradi naključnosti v naključnih algoritmih se lahko vedenje algoritma spremeni tudi pri istem vhodu (pri različnih izvedbah algoritma). Toda to v rekurzivnih algoritmih ni mogoče in vedenje rekurzivnega algoritma bi bilo enako za fiksni vhod.
