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. Vďaka tejto náhodnosti sa správanie algoritmu môže zmeniť aj pri pevnom vstupe. Pre mnohé problémy poskytujú randomizované algoritmy najjednoduchšie a najúčinnejšie riešenia. Rekurzívne algoritmy sú založené na myšlienke, že riešenie problému možno nájsť hľadaní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 informatike a mnoho programovacích jazykov na vysokej úrovni podporuje rekurziu.
Čo je to náhodný algoritmus?
Randomizované algoritmy obsahujú zmysel pre náhodnosť tým, že robia náhodné voľby, ktoré riadia vykonávanie algoritmu. Zvyčajne sa to robí tak, že sa ako dodatočný vstup vezme množina náhodných čísel generovaných generátorom pseudonáhodných čísel. V dôsledku toho sa správanie algoritmu môže zmeniť aj pri pevnom vstupe. Quicksort je všeobecne známy algoritmus, ktorý používa koncept náhodnosti a má dobu chodu O(n log n) bez ohľadu na vstupné vlastnosti. Ďalej sa metóda náhodnej prírastkovej konštrukcie používa na budovanie konštrukcií, ako je konvexný trup vo výpočtovej geometrii. Pri tejto metóde sú vstupné body náhodne permutované a potom vložené 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äčšou výzvou pri navrhovaní randomizovaného algoritmu je vykonávanie asymptotickej analýzy časovej a priestorovej zložitosti.
Čo je rekurzívny algoritmus?
Rekurzívne algoritmy sú založené na myšlienke, že riešenie problému možno nájsť hľadaním riešení menších čiastkových problémov rovnakého problému. V rekurzívnom algoritme je funkcia definovaná z hľadiska predchádzajúcej verzie samej seba. Je dôležité poznamenať, že toto samoodkazovanie by malo mať podmienku ukončenia, aby sa zabránilo odkazovaniu na seba navždy. Pred samotným odkazovaním sa skontroluje podmienka ukončenia. Počiatočný krok rekurzívneho algoritmu súvisí so základnou klauzulou rekurzívnej definície problému. Kroky, ktoré nasledujú po úvodnom kroku, súvisia s induktívnymi vetami problému. Rekurzívne algoritmy poskytujú v mnohých situáciách jednoduchšie riešenie a sú bližšie k prirodzenému spôsobu myslenia ako iteračný algoritmus pre rovnaký 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é využívajú zmysel pre náhodnosť tým, že robia náhodné voľby, 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šenia menších čiastkových problémov rovnakého problému. V dôsledku náhodnosti v náhodných algoritmoch sa správanie algoritmu môže zmeniť aj pre rovnaký vstup (v rôznych vykonaniach algoritmu). Ale to nie je možné v rekurzívnych algoritmoch a správanie rekurzívneho algoritmu by bolo rovnaké pre pevný vstup.
