Rozdiel medzi náhodným a rekurzívnym algoritmom

Randomizovaný vs rekurzívny algoritmus

Randomizované algoritmy začleňujú do svojej logiky pocit náhodnosti výberom náhodných výberov počas vykonávania algoritmu. V dôsledku tejto náhodnosti sa správanie algoritmu môže zmeniť dokonca aj pri pevnom vstupe. V prípade mnohých problémov poskytujú randomizované algoritmy najjednoduchšie a najefektívnejšie riešenia. Rekurzívne algoritmy sú založené na myšlienke, že riešenie problému možno nájsť nájdením riešení menších čiastkových problémov toho istého problému. Rekurzia sa široko používa na nájdenie riešení problémov v oblasti informatiky a rekurzia podporuje mnoho programovacích jazykov na vysokej úrovni.

Čo je to náhodný algoritmus?

Randomizované algoritmy zahŕňajú pocit náhodnosti výberom náhodných výberov, ktoré usmerňujú vykonanie algoritmu. Obvykle sa to robí tak, že sa ako ďalší vstup vyberie množina náhodných čísel generovaných generátorom pseudonáhodných čísel. Z tohto dôvodu sa správanie algoritmu môže zmeniť dokonca aj pri pevnom vstupe. Quicksort je všeobecne známy algoritmus, ktorý používa koncept náhodnosti a má prevádzkovú dobu O (n log n) bez ohľadu na vstupné vlastnosti. Ďalej sa pre stavebné konštrukcie, ako je konvexný trup vo výpočtovej geometrii, používa metóda náhodného zvyšovania. Pri tejto metóde sa vstupné body náhodne permutujú a potom sa postupne vkladajú do štruktúry. Implementácia randomizovaného algoritmu je relatívne jednoduchá ako implementácia deterministického algoritmu pre ten istý problém. Najväčšou výzvou pri navrhovaní randomizovaného algoritmu je vykonávanie asymptotickej analýzy zložitosti času a priestoru.

Čo je rekurzívny algoritmus?

Rekurzívne algoritmy sú založené na myšlienke, že riešenie problému možno nájsť nájdením riešení menších čiastkových problémov toho istého problému. V rekurzívnom algoritme je funkcia definovaná ako predchádzajúca verzia. Je dôležité si uvedomiť, že toto samoreferencovanie by malo mať podmienku ukončenia, aby sa navždy neodkazovalo. Podmienka ukončenia je skontrolovaná pred samotným odkazom. Počiatočný krok rekurzívneho algoritmu súvisí so základnou doložkou rekurzívnej definície problému. Kroky, ktoré nasledujú po počiatočnom kroku, sa týkajú induktívnych klauzúl problému. Rekurzívne algoritmy poskytujú jednoduchšie riešenie v mnohých situáciách a sú bližšie k prirodzenému spôsobu myslenia ako iteračný algoritmus pre ten istý problém. Vo všeobecnosti však rekurzívne algoritmy vyžadujú viac pamäte a sú výpočtovo drahé.

Aký je rozdiel medzi randomizovaným a rekurzívnym algoritmom?

Náhodné algoritmy sú algoritmy, ktoré používajú zmysel pre náhodnosť výberom náhodných výberov, ktoré by mohli ovplyvniť vykonanie algoritmu, zatiaľ čo rekurzívne algoritmy sú algoritmy, ktoré sú založené na myšlienke, že riešenie problému možno nájsť nájdením riešení menších čiastkových problémov. rovnakého problému. V dôsledku náhodnosti v náhodných algoritmoch by sa správanie algoritmu mohlo zmeniť dokonca aj pri rovnakom vstupe (pri rôznych spusteniach algoritmu). To však nie je možné v rekurzívnych algoritmoch a správanie rekurzívneho algoritmu by bolo rovnaké pre pevný vstup.