Skirtumas tarp atsitiktinio ir rekursinio algoritmo

Atsitiktinis vs rekursyvus algoritmas

Atsitiktiniai algoritmai įtraukia atsitiktinumo jausmą į savo logiką, atsitiktinai pasirinkdami algoritmo vykdymo metu. Dėl šio atsitiktinumo algoritmo elgsena gali pasikeisti net ir fiksuoto įėjimo atveju. Dėl daugelio problemų atsitiktiniai algoritmai pateikia paprasčiausius ir efektyviausius sprendimus. Rekursyvūs algoritmai grindžiami mintimi, kad problemos sprendimą galima rasti ieškant tos pačios problemos mažesnių antrinių problemų sprendimų. Rekursija plačiai naudojama ieškant informatikos problemų sprendimų, o rekursiją palaiko daugelis aukšto lygio programavimo kalbų.

Kas yra atsitiktinis algoritmas?

Atsitiktiniai algoritmai įtraukia atsitiktinumo pojūtį, pasirinkdami atsitiktinius atsitikimus, kurie vadovaujasi algoritmo vykdymu. Paprastai tai daroma imant atsitiktinių skaičių rinkinį, kurį generuoja pseudo-atsitiktinių skaičių generatorius, kaip papildomą įvestį. Dėl šios priežasties algoritmo elgsena gali pasikeisti net ir fiksuoto įėjimo atveju. „Quicksort“ yra plačiai žinomas algoritmas, kuris naudoja atsitiktinumo sąvoką ir jo veikimo laikas yra O (n log n), nepaisant įvesties savybių. Be to, statybinėms konstrukcijoms, tokioms kaip išgaubtas korpusas, skaičiavimo geometrijoje naudojamas atsitiktinės atrankos laipsniškas konstrukcijos metodas. Taikant šį metodą, įvesties taškai yra atsitiktinai permutuojami ir po vieną įstatomi į struktūrą. Įdiegti atsitiktinių imčių algoritmą yra gana paprasta, nei įgyvendinti deterministinį tos pačios problemos algoritmą. Didžiausias iššūkis kuriant atsitiktinių imčių algoritmą yra asimptotinė laiko ir erdvės sudėtingumo analizė.

Kas yra rekursinis algoritmas?

Rekursyvūs algoritmai grindžiami mintimi, kad problemos sprendimą galima rasti ieškant tos pačios problemos mažesnių antrinių problemų sprendimų. Rekursyviniame algoritme funkcija apibrėžiama pagal ankstesnę jos versiją. Svarbu atkreipti dėmesį į tai, kad šis savęs nurodymas turėtų būti nutraukimo sąlyga, kad būtų išvengta nuorodų amžiams. Nutraukimo sąlyga patikrinama prieš pradedant nuorodą. Pradinis rekursinio algoritmo žingsnis yra susijęs su rekursinio problemos apibrėžimo pagrindine sakiniu. Žingsniai, kurie seka pradinį žingsnį, yra susiję su induktyviaisiais problemos sakiniais. Rekursyvūs algoritmai daugelyje situacijų suteikia paprastesnį sprendimą ir yra artimesni natūraliam mąstymo būdui, nei iteracinis tos pačios problemos algoritmas. Bet paprastai rekursyviems algoritmams reikia daugiau atminties ir jie skaičiavimo požiūriu yra brangūs.

Kuo skiriasi atsitiktinis ir rekursinis algoritmas?

Atsitiktiniai algoritmai yra algoritmai, kurie naudoja atsitiktinumo pobūdį, darydami atsitiktinius pasirinkimus, kurie galėtų paveikti algoritmo vykdymą, o rekursyvūs algoritmai yra algoritmai, pagrįsti idėja, kad problemos sprendimą galima rasti ieškant mažesnių antrinių problemų sprendimų. tos pačios problemos. Dėl atsitiktinių algoritmų atsitiktinumų, algoritmo elgsena gali pasikeisti net ir tuo pačiu įėjimu (skirtinguose algoritmo vykdymuose). Bet tai neįmanoma rekursyviniuose algoritmuose ir fiksuoto įėjimo atveju rekursinis algoritmas elgtųsi vienodai..