Randomizovaný vs rekurzivní algoritmus
Randomizované algoritmy začleňují do své logiky pocit náhodnosti tím, že během provádění algoritmu provádějí náhodné volby. Díky této náhodnosti se chování algoritmu může změnit i pro pevný vstup. Pro mnoho problémů poskytují randomizované algoritmy nejjednodušší a nejefektivnější řešení. Rekurzivní algoritmy jsou založeny na myšlence, že řešení problému lze nalézt nalezením řešení menších dílčích problémů stejného problému. Rekurze je široce používána k nalezení řešení problémů v informatice a mnoho programovacích jazyků na vysoké úrovni podporuje rekurzi.
Co je to randomizovaný algoritmus?
Randomizované algoritmy zahrnují pocit náhodnosti tím, že dělají 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. Díky tomu 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á dobu běhu O(n log n) bez ohledu na vstupní vlastnosti. Dále se metoda randomizované inkrementální konstrukce používá pro stavební konstrukce, jako je konvexní trup ve výpočetní geometrii. 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 časové a prostorové složitosti.
Co je rekurzivní algoritmus?
Rekurzivní algoritmy jsou založeny na myšlence, že řešení problému lze nalézt nalezením řešení menších dílčích problémů stejného problému. V rekurzivním algoritmu je funkce definována v podmínkách dřívější verze sebe sama. Je důležité poznamenat, že toto samoodkazování by mělo mít podmínku ukončení, aby se zabránilo odkazování na sebe navždy. Před samotným odkazem je zkontrolována 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 prvním kroku, souvisí s induktivními klauzulemi problému. Rekurzivní algoritmy poskytují v mnoha situacích jednodušší řešení a blíží se přirozenému způsobu myšlení než iterativní algoritmus pro stejný problém. Obecně však rekurzivní algoritmy vyžadují více paměti a jsou výpočetně drahé.
Jaký je rozdíl mezi randomizovaným a rekurzivním algoritmem?
Náhodné algoritmy jsou algoritmy, které využívají pocit náhodnosti tím, že dělají náhodné volby, které by mohly ovlivnit provedení algoritmu, zatímco rekurzivní algoritmy jsou algoritmy založené na myšlence, že řešení problému lze nalézt nalezením řešení menších dílčích problémů stejného problému. Díky náhodnosti v náhodných algoritmech se chování algoritmu může 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.
