Randomizovaný vs rekurzivní algoritmus
Randomizované algoritmy začleňují do své logiky pocit náhodnosti tím, že provádějí náhodné volby během provádění algoritmu. Kvůli této náhodnosti se chování algoritmu může změnit i pro pevný vstup. U mnoha problémů poskytují randomizované algoritmy nejjednodušší a nejúčinnější řešení. Rekurzivní algoritmy jsou založeny na myšlence, že řešení problému lze nalézt hledáním řešení menších dílčích problémů stejného problému. Rekurze je široce používána k hledání řešení problémů v informatice a mnoho rekurze podporuje mnoho programovacích jazyků na vysoké úrovni.
Co je to randomizovaný algoritmus?
Randomizované algoritmy zahrnují pocit náhodnosti tím, že provádějí náhodné volby, které řídí provádění algoritmu. To se obvykle provádí tak, že se jako další vstup vezme sada náhodných čísel generovaných generátorem pseudonáhodných čísel. Z tohoto důvodu se chování algoritmu může změnit i pro pevný vstup. Quicksort je široce známý algoritmus, který používá koncept náhodnosti a má provozní dobu O (n log n) bez ohledu na vstupní vlastnosti. Dále se pro vytváření konstrukcí, jako je konvexní trup, ve výpočetní geometrii používá metoda randomizované přírůstkové konstrukce. V této metodě jsou vstupní body náhodně permutovány a poté vkládány jeden po druhém do struktury. Implementace randomizovaného algoritmu je relativně jednoduchá než implementace deterministického algoritmu pro stejný problém. Největší výzva při navrhování randomizovaného algoritmu spočívá v provádění asymptotické analýzy pro časovou a prostorovou složitost.
Co je to rekurzivní algoritmus?
Rekurzivní algoritmy jsou založeny na myšlence, že řešení problému lze nalézt hledáním řešení menších dílčích problémů stejného problému. V rekurzivním algoritmu je funkce definována z hlediska dřívější verze samotné. Je důležité si uvědomit, že toto vlastní odkazování by mělo mít podmínku ukončení, aby se zabránilo navždy odkazování na sebe. Před ukončením odkazu se zkontroluje podmínka ukončení. Počáteční krok rekurzivního algoritmu souvisí se základní klauzulí rekurzivní definice problému. Kroky, které následují po počátečním kroku, souvisejí s indukčními klauzulemi problému. Rekurzivní algoritmy poskytují v mnoha situacích jednodušší řešení a jsou blíže přirozenému způsobu myšlení než iterativní algoritmus pro stejný problém. Ale obecně,rekurzivní algoritmy vyžadují více paměti a jsou výpočetně nákladné.
Jaký je rozdíl mezi randomizovaným a rekurzivním algoritmem?
Náhodné algoritmy jsou algoritmy, které využívají smysl pro náhodnost tím, že provádějí náhodné volby, které by mohly ovlivnit provedení algoritmu, zatímco rekurzivní algoritmy jsou algoritmy, které jsou založeny na myšlence, že řešení problému lze nalézt hledáním řešení menších dílčích problémů stejného problému. Kvůli náhodnosti v náhodných algoritmech se chování algoritmu mohlo změnit i pro stejný vstup (v různých provedeních algoritmu). Ale to není možné v rekurzivních algoritmech a chování rekurzivního algoritmu by bylo stejné pro pevný vstup.
