Operace A nad dynamickou datovou strukturou má v daném kontextu svého provádění amortizovanou časovou složitost $O(f (n))$ (značíme $O^∗(f(n)))$, pokud posloupnost $k$ operací $A$ má celkovou časovou složitost $O(k · f (n))$. Parametr $n$ je velikost dynamické množiny po provedení této posloupnosti operací.
Algoritmus 7.1: Algoritmus NPInsert $(P, x)$
Časová složitost volání NPInsert na pole s $k$ prvky je v nejhorším případě $Θ(k)$.
Uvažujme na počátku prázdné nafukovací pole.
Potom celková časová složitost posloupnosti $n$ operací NPInsert je $Θ(n)$,
neboli amortizovaná složitost operace NPInsert je $Θ^∗(1)$.
Práce sestává z vkládání jednotlivých prvků (každý v $O(1)$ čase) proložených zvětšováním pole.
Celkový čas samotného vkládání je tedy $Θ(n)$.
Případné zvětšování při vložení $i$-tého prvku trvá čas $Θ(i)$.
Ke zvětšování dochází právě tehdy, když $i$ je mocnina dvou.
Všechna zvětšení tedy dohromady stojí $Θ(20 + 21 + · · · + 2k)$, kde $2k$ je nejvyšší mocnina dvojky menší než $n$.
V závorce je geometrická posloupnost se součtem $2k+1 − 1 < 2n$.
Celková časová složitost proto činí $Θ(n)$.
$\square$
Binární sčítačka je obvod, který uchovává bitovou reprezentaci čísla uloženou v buňkách nastavitelných na 0 nebo 1.Uvažujeme $k$-bitovou sériovou sčítačku (ripple-carry):
přenos se postupně šíří zprava doleva
Po zapnutí má sčítačka všechny bity nastaveny na 0.
Sčítačka podporuje dvě operace:
Inc ($n$) zvýší číslo $n$ reprezentované v sčítačce o 1.
Add ($n, m$) přičte k číslu v sčítačce $n$ binární číslo $m$.
TODO ukazka prezentace 4 slajd 39?
Složitost operace Inc ($n$) $k$-bitové sériové sčítačky je v nejhorším případě $≤ k$.
Uvažujme na počátku vynulovanou binární sčítačku.
Potom celková složitost posloupnosti $n$ volání operace Inc měřená počtem bitových inverzí je $O(n)$,
neboli amortizovaná složitost Inc je $O^∗(1)$.
Bankéřova neboli účetní metoda.
Počet inverzí při jedné operaci Inc ($n$) je od 1 do log $n$ (závisí na bitovém rozvoji čísla $n$).
Každé operaci Inc přiřadíme virtuální kredit ve formě 2 mincí $⋆$.
Za každou inverzi zaplatíme 1 mincí.
Pokud existují nespotřebované mince, bude je Inc střádat pro budoucí
inverze více bitů do zásoby tak, že na každém jedničkovém bitu si uchová jednu minci.
Tedy třeba takto (čárka nad čísly značí minci $⋆$):
Inc vždy invertuje zprava od lsb jedničkové bity na nulové tak dlouho,
dokud nenarazí na první nulový bit, který invertuje na jedničkový a tím řetěz inverzí skončí.
Inverze všech takových jedničkových bitů zaplatíme z nastřádaných mincí $⋆$ ležících na každém z nich.
Z kreditu dvou mincí ⋆ přidělených této operaci Inc spotřebujeme
1 jednu minci na inverzi první nuly zprava na jedničku a
2 druhou minci $⋆$ položíme do zásoby na právě vzniklou jedničku.
Náš příklad se tedy změní takto:
Operace Inc tudíž zachovává následující invariant: po skončení každé operace Inc je na každém jedničkovém bitu čísla sčítačky našetřena jedna $⋆$.
To znamená, že celkový počet inverzí v posloupnosti $n$ Inců provedených za sebou lze zaplatit nejvýše $2n$ mincemi $⋆$.
Čili amortizovaná složitost operace Inc je $O^∗(1)$.
$\square$