Please enable JavaScript.
Coggle requires JavaScript to display documents.
18. Rekurzivní algoritmy (Metoda rozděl a panuj (výhody (efektivnost…
18. Rekurzivní algoritmy
Metoda rozděl a panuj
- po dosažení určité úrovně provádíme zadané operace (využíváme malé velikosti dat)
- rozdělené části opět spojujeme, přo zachování určitých podmínek (setříděnost,...)
- problém rekurzivně dělíme na menší části
použití
-
hledání 2 bodů z n, které mají mezi sebou nejmenší vzdálenost
třídění (mergesort, quicksort)
-
-
výhody
-
-
-
přístup k paměti (řešení v cache, ne pomalejší hlavní)
-
-
nevýhody
-
explicitní stack
možná nerekurzivní implementace (podproblémy do datové strukt. - zásobník, fronta, prioritní fronta)
-
-
Odstranění rekurze
nahrazení vlastním zásobníkem / jinou dat. strukturou (fronta, prior. fronta,...) - vždy
-
-
-
-
-
-
-
-
-
-