Atsitiktinis vs rekursyvus algoritmas
Atsitiktiniai algoritmai savo logikoje įtraukia atsitiktinumo jausmą, nes atlieka atsitiktinius pasirinkimus algoritmo vykdymo metu. Dėl šio atsitiktinumo algoritmo elgsena gali pasikeisti net fiksuotai įvesties atveju. Daugeliui problemų atsitiktinių imčių algoritmai pateikia pačius paprasčiausius ir efektyviausius sprendimus. Rekursyviniai algoritmai yra pagrįsti idėja, kad problemos sprendimą galima rasti ieškant sprendimų mažesnėms tos pačios problemos antrinėms problemoms. Rekursija plačiai naudojama ieškant kompiuterių mokslo problemų sprendimų, o daugelis aukšto lygio programavimo kalbų palaiko rekursiją.
Kas yra atsitiktinis algoritmas?
Atsitiktiniai algoritmai apima atsitiktinumo pojūtį, nes pasirenkami atsitiktiniai pasirinkimai, kuriais vadovaujamasi vykdant algoritmą. Paprastai tai daroma kaip papildomą įvestį imant atsitiktinių skaičių rinkinį, sugeneruotą pseudoatsitiktinių skaičių generatoriaus. Dėl šios priežasties algoritmo elgsena gali pasikeisti net naudojant fiksuotą įvestį. Greitasis rūšiavimas yra plačiai žinomas algoritmas, kuris naudoja atsitiktinumo sąvoką ir kurio veikimo laikas yra O (n log n), nepaisant įvesties savybių. Be to, atsitiktinės atrankos laipsniškas konstravimo metodas naudojamas statybinėms konstrukcijoms, tokioms kaip išgaubtas korpusas skaičiavimo geometrijoje. Taikant šį metodą, įvesties taškai yra atsitiktinai permutuojami ir po vieną įterpiami į struktūrą. Įgyvendinti atsitiktinių imčių algoritmą yra gana paprasta nei įgyvendinti deterministinį algoritmą tai pačiai problemai spręsti. Didžiausias iššūkis kuriant atsitiktinių imčių algoritmą yra atlikti asimptotinę laiko ir erdvės sudėtingumo analizę.
Kas yra rekursinis algoritmas?
Rekursyviniai algoritmai yra pagrįsti idėja, kad problemos sprendimą galima rasti ieškant sprendimų mažesnėms tos pačios problemos antrinėms problemoms. Rekursyviniame algoritme funkcija apibrėžiama pagal ankstesnę jos versiją. Svarbu pažymėti, kad ši nuoroda į save turėtų turėti nutraukimo sąlygą, kad būtų išvengta nuorodų į save amžinai. Nutraukimo sąlyga patikrinama prieš pateikiant nuorodą. Pradinis rekursinio algoritmo žingsnis yra susijęs su rekursinio problemos apibrėžimo baziniu sakiniu. Veiksmai, einantys po pradinio žingsnio, yra susiję su indukciniais problemos sakiniais. Rekursyvūs algoritmai daugelyje situacijų pateikia paprastesnį sprendimą ir yra artimesni natūraliam mąstymo būdui nei iteracinis tos pačios problemos algoritmas. Tačiau apskritai rekursiniams algoritmams reikia daugiau atminties ir jie yra brangūs.
Kuo skiriasi atsitiktinis algoritmas nuo rekursyvaus?
Atsitiktiniai algoritmai yra algoritmai, kurie naudoja atsitiktinumo pojūtį priimdami atsitiktinius pasirinkimus, kurie gali turėti įtakos algoritmo vykdymui, o rekursiniai algoritmai yra algoritmai, pagrįsti idėja, kad problemos sprendimą galima rasti surandant mažesnių tos pačios problemos subproblemų sprendimai. Dėl atsitiktinumo atsitiktiniuose algoritmuose algoritmo elgsena gali pasikeisti net ir tai pačiai įvesties atveju (skirtingai vykdant algoritmą). Tačiau tai neįmanoma naudojant rekursinius algoritmus, o rekursinio algoritmo elgsena būtų tokia pati, kai įvestis yra fiksuota.
