04 Amortizovaná analýza
$$
\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}}
$$
# Amortizovaná analýza
# Amortizovaná časová složitost
Označuje časovou složitost algoritmu v sekvenci nejhorších vstupních dat
Na rozdíl od průměrné složitosti nevyužívá pravděpodobnosti a je proto zaručená
Jedná se jakoby o průměrnou složitost
Na rozdíl od asymptotické složitosti, která bere nejhorší možný čas
Označujeme $O^{*}(\space)$
Asymptotickou složitost $O(\space)$
K vypočtení se může použít Účetní metoda:
- Každé operaci je přiřazena amortizovaná a skutečná cena
- Pokud je amortizovaná větší, tak rozdíl vložíme na společný účet
- Je li skutečná větší, tak rozdíl z účtu odebereme
- V každém okamžiku musí být zůstatek na účtu nezáporný
# Nafukovací pole
- Některé inserty budou dlouhé (potřeba nafouknout a překopírovat pole)
- Některé budou velmi rychlé
- Amortizovaná složitost pro 1 insert je ale $\Theta^*(1)$
- U asymptotické mohl být 1 insert klidně až $O(n)$, pokud bychom vkládali až na konec pole
- Časová složitost pro pole s $i$ prvky je v nejhorším případě $\Theta(i)$