Randomizovaný vs rekurzívny algoritmus
Randomizované algoritmy začleňujú do svojej logiky zmysel pre náhodnosť tým, že robia náhodné voľby počas vykonávania algoritmu. Kvôli tejto náhodnosti sa správanie algoritmu môže meniť aj pri pevnom vstupe. Pri mnohých problémoch 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šenia menších čiastkových problémov rovnakého problému. Rekurzia sa často používa na hľadanie riešení problémov v oblasti informatiky a mnoho rekurzií podporuje vysoké programovacie jazyky.
Čo je to randomizovaný algoritmus?
Randomizované algoritmy zahŕňajú zmysel pre náhodnosť uskutočňovaním náhodných rozhodnutí, ktoré vedú pri vykonávaní algoritmu. To sa zvyčajne deje tak, že sa ako ďalší vstup použije skupina náhodných čísel generovaných generátorom pseudonáhodných čísel. Z tohto dôvodu sa správanie algoritmu môže meniť aj pri pevnom vstupe. Quicksort je všeobecne známy algoritmus, ktorý využíva koncept náhodnosti a má prevádzkovú dobu O (n log n) bez ohľadu na vstupné vlastnosti. Ďalej sa vo výpočtovej geometrii pre budovanie štruktúr, ako je konvexný trup, používa metóda náhodnej prírastkovej konštrukcie. V tejto metóde sú vstupné body náhodne permutované a potom vkladané jeden po druhom do štruktúry. Implementácia randomizovaného algoritmu je relatívne jednoduchá ako implementácia deterministického algoritmu pre rovnaký problém. Najväčšia výzva pri navrhovaní randomizovaného algoritmu spočíva v uskutočňovaní asymptotickej analýzy pre časovú a priestorovú zložitosť.
Čo je to 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šenia menších čiastkových problémov rovnakého problému. V rekurzívnom algoritme je funkcia definovaná z hľadiska staršej verzie. Je dôležité si uvedomiť, že toto samo referencovanie by malo mať podmienku ukončenia, aby sa zabránilo navždy referencovaniu. Podmienka ukončenia sa skontroluje pred odkazom na ňu. 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, súvisia s indukčnými klauzulami problému. Rekurzívne algoritmy poskytujú jednoduchšie riešenie v mnohých situáciách a majú bližšie k prirodzenému spôsobu myslenia ako iteračný algoritmus pre ten istý problém. Ale všeobecne,rekurzívne algoritmy vyžadujú viac pamäte a sú výpočtovo nákladné.
Aký je rozdiel medzi randomizovaným a rekurzívnym algoritmom?
Náhodné algoritmy sú algoritmy, ktoré využívajú zmysel pre náhodnosť pri náhodných voľbách, ktoré by mohli ovplyvniť vykonávanie 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šenia menších čiastkových problémov. rovnakého problému. Kvôli náhodnosti v náhodných algoritmoch sa správanie algoritmu mohlo zmeniť aj pre ten istý vstup (v rôznych uskutočneniach algoritmu). Ale to nie je možné v rekurzívnych algoritmoch a správanie rekurzívneho algoritmu by bolo rovnaké pre pevný vstup.
