Randomizuotas ir rekursinis algoritmas
Atsitiktinių imčių algoritmai į savo logiką įtraukia atsitiktinumo jausmą, atsitiktinai pasirinkdami vykdydami algoritmą. Dėl šio atsitiktinumo algoritmo elgesys gali pasikeisti net ir fiksuoto įvesties atveju. Daugeliui problemų atsitiktinių imčių algoritmai pateikia paprasčiausius ir efektyviausius sprendimus. Rekursiniai algoritmai yra pagrįsti idėja, kad problemos sprendimą galima rasti ieškant mažesnių tos pačios problemos antrinių problemų sprendimų. Rekursija yra plačiai naudojama norint rasti kompiuterių mokslo problemų sprendimus, o daugelis aukšto lygio programavimo kalbų palaiko rekursiją.
Kas yra atsitiktinių imčių algoritmas?
Atsitiktinių imčių algoritmai įtraukia atsitiktinumo jausmą, padarydami atsitiktinius pasirinkimus, kuriais vadovaujamasi vykdant algoritmą. Tai paprastai daroma imant atsitiktinių skaičių rinkinį, kurį sugeneruoja pseudo atsitiktinių skaičių generatorius, kaip papildomą įvestį. Dėl to algoritmo elgesys gali pasikeisti net ir fiksuoto įvesties atveju. „Quicksort“yra plačiai žinomas algoritmas, kuris naudoja atsitiktinumo sąvoką, o jo veikimo laikas yra O (n log n), neatsižvelgiant į įvesties savybes. Be to, skaičiavimo geometrijoje statybinėms konstrukcijoms, tokioms kaip išgaubtas korpusas, naudojamas atsitiktinių imčių laipsniškas konstrukcijos metodas. Taikant šį metodą, įvesties taškai yra atsitiktinai išdėstyti ir po vieną įterpiami į struktūrą. Atsitiktinių imčių algoritmo įgyvendinimas yra gana paprastas nei tos pačios problemos deterministinio algoritmo įgyvendinimas. Didžiausias iššūkis kuriant atsitiktinių imčių algoritmą yra asimptotinės laiko ir erdvės sudėtingumo analizė.
Kas yra rekursinis algoritmas?
Rekursiniai algoritmai yra pagrįsti idėja, kad problemos sprendimą galima rasti ieškant mažesnių tos pačios problemos antrinių problemų sprendimų. Rekursyviame algoritme funkcija apibrėžiama pagal ankstesnę jos versiją. Svarbu pažymėti, kad ši nuoroda į save turėtų turėti nutraukimo sąlygą, kad amžinai nebūtų galima kreiptis į save. Nutraukimo sąlyga patikrinama prieš pateikiant nuorodą į save. Pradinis rekursiškojo algoritmo žingsnis yra susijęs su rekursinio problemos apibrėžimo pagrindiniu sakiniu. Pradiniai žingsniai yra susiję su indukcinėmis problemos išlygomis. Rekursiniai algoritmai suteikia paprastesnį sprendimą daugelyje situacijų ir yra arčiau natūralaus mąstymo būdo nei iteracinis tos pačios problemos algoritmas. Bet apskritairekursiškiems algoritmams reikia daugiau atminties ir jie yra brangūs skaičiavimams.
Koks skirtumas tarp atsitiktinių imčių ir rekursinių algoritmų?
Atsitiktiniai algoritmai yra algoritmai, kurie naudoja atsitiktinumo jausmą, pasirinkdami atsitiktinius pasirinkimus, kurie gali turėti įtakos algoritmo vykdymui, o rekursiniai algoritmai yra algoritmai, paremti idėja, kad problemos sprendimą galima rasti ieškant mažesnių problemų tos pačios problemos. Dėl atsitiktinių algoritmų atsitiktinumo algoritmo elgsena gali pasikeisti net tam pačiam įėjimui (skirtingose algoritmo vykdymo vietose). Bet tai neįmanoma rekursiškuose algoritmuose, o rekursinio algoritmo elgsena fiksuoto įvesties atveju būtų tokia pati.
