08.1 Rekurze
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Rekurze
Viz Rekurze
- Např. MergeSort
- Strom rekurzivních volání
- Střední hodnota - $\mathrm{\boldsymbol{E}} , [T_i]$
# Rekurzivní formulace násobení 2 čísel
- Karacubův algoritmus
- Nahrazení 4 rekurzivních volání za 3
- Má $\log n$ pater, protože vstup vždy dělíme na poloviny
# Strassenův algoritmus
- Zrychlení násobení matic
- Na stejném principu jako Karacubův algoritmus