Amortizovaná časová složitost je v něčem podobná časové složitosti v průměrném případě. Podává lepší informaci o algoritmu než časová složitost v nejhorším případě, ale tentokrát nepotřebujeme nic počítat přes všechny možné vstupy, nepotřebujeme používat žádnou pravděpodobnost.

Když pracujeme s datovou strukturou (například s polem), tak můžeme veškerou práci s datovou strukturou realizovat pomocí několika operací. Operace je něco jako funkce pro práci s datovou strukturou. Operace provedou, co potřebujeme, a odstíní nás od znalosti fungování datové strukury. Příkladem operace pro práci s polem je vložení prvku do pole, smazání prvku, nalezení minima, apod.

Definice (Amortizovaná časová složitost): Je dána datová struktura $D$, na které postupně provádíme posloupnost stejných operací. Začneme s $D_0:=D$. První operace zavolaná na $D_0$ upraví datovou strukturu na $D_1$. Druhá operace zavolaná na $D_1$ upraví datovou strukturu na $D_2$. A tak dále. Postupně zavoláme $i$-tou operaci na $D_{i-1}$ a ta upraví datovou strukturu na $D_i$. Některá operace může trvat krátce, jiná déle. Průměrný čas doby trvání operace nazveme amortizovanou časovou složitostí. Amortizovanou časovou složitost jedné operace spočítáme tak, že spočteme celkovou časovou složitost posloupnosti operací v nejhorším případě a vydělíme ji počtem operací.

K čemu je amortizovaná časová složitost? Pomůže nám lépe odhadnout časovou složitost některých algoritmů v nejhorším případě.

Příklad: Máme algoritmus, který používá jen jednu datovou strukturu a $n$ krát volá operaci, která tuto datovou strukturou upravuje. Nic jiného nedělá. Časová složitost operace je v nejhorším případě $\OO(n)$, ale její amortizovaná časová složitost je jen $\OO(\log n)$. Celkovou časovou složitost celého algoritmu můžeme spočítat jako $n \cdot \OO(n) =\OO(n^2)$. To ale může být mnohem více než skutečná časová složitost algoritmu. Druhá možnost odhadu časové složitosti je s pomocí amortizované časové složitosti. Ikdyž bude jeden konkrétní průběh operace trvat $\OO(n)$, můžeme odhadnout časovou složitost algoritmu v nejhorším případě jako $n$ krát amortizovaná časová složitost jedné operace. To je jen $\OO(n\log n)$.

Výpočet amortizované časové složitosti. K výpočtu amortizované časové složitosti jedné operace se nejčastěji používají následující metody. Pro lepší pochopení metod se podívejte na konkrétní příklady výpočtu v následujících podsekcích.

  1. Přímo z definice.Spočteme časovou složitost posloupnosti $n$ operací v nejhorším případě a podělíme ji $n$.
  2. Účetní metoda. Předpokládejme, že uhodneme, kolik je amortizovaná časová složitost operace. Jak ověřit, že je to pravda? Představme si výpočet na stroji, kde musíme za každou časovou jednotku strávenou výpočtem zaplatit jednu korunu. Na začátku přidělíme každé operaci1 tolik korun, kolik je její amortizovaná složitost. V algoritmu pracujeme s objekty jako je vrchol, hrana, políčko pole,\dots Každému objektu otevřeme účet.Pokud bude operace trvat kratší čas, než kolik je její amortizovaná složitost, tak zaplatí za svůj výpočet a ještě jí zbydou peníze. Ty uloží na účty objektů, na kterých pracuje. Pokud bude naopak trvat delší čas, než je její amortizovaná složitost, tak si peníze sebere z účtů objektů, na kterých pracuje. Díky tomu bude moci zaplatit za svůj výpočet.Metoda spočívá v nalezení takových pravidel ukládání a vybírání peněz z účtů, aby se žádný účet nedostal do mínusu a abychom byli schopni zaplatit za všechnu vykonanou práci. Pokud se nám to povede, tak pomocí pravidel ověříme, že je náš odhad hodnoty amortizované časové složitosti správný.
  3. Metoda potenciálu. Využijeme účtů z účetní metody. Potenciál je celkový vklad v bance, kde máme účty. Jinými slovy je to součet aktuálních hodnot vkladů na všech účtech.Pojďme si to ale vysvětlit pořádně. Nechť $a$ je amortizovaná cena jedné operace. Začneme s datovou strukturou $D_0$ a postupně budeme provádět $n$ operací. Nechť $c_i$ je skutečná cena provedení $i$-té operace a $D_i$ je datová struktura, která vznikla z $D_{i-1}$ zavoláním $i$-té operace. Potenciální funkce $\Phi$ přiřazuje každé datové struktuře $D_i$ reálné číslo $\Phi(D_i)$, které nazveme potenciál spojený s datovou strukturou $D_i$. Každá operace dostala tolik korun, kolik je její amortizovaná složitost. Pokud trvala kratší čas, než je její amortizovaná časová složitost, tak ušetřila peníze. Ušetřené peníze vloží do banky. Tím se zvýší potenciál (vklad v bance) o $\Phi(D_i)-\Phi(D_{i-1})$. Pokud operace trvala déle, než je její amortizovaná složitost, tak si peníze z banky naopak vybrala. V tomto případě je potenciálový rozdíl $\Phi(D_i)-\Phi(D_{i-1})$ záporný. Amortizovaná cena $i$-té operace vzhledem k potenciálu $\Phi$ je $a=c_i+\Phi(D_i)-\Phi(D_{i-1})$.Celková amortizovaná cena všech $n$ operací je $\sum_{i=1}^n
    (c_i+\Phi(D_i)-\Phi(D_{i-1}))= \sum_{i=1}^n c_i+\Phi(D_n)-\Phi(D_0)$. Pokud skončíme s $\Phi(D_n)-\Phi(D_0)\geq 0$, tak nám na účtech zůstaly ještě nějaké penízky a amortizovaná časová složitost všech $n$ operací je horním odhadem časové složitosti. Pokud skončíme s $\Phi(D_n)-\Phi(D_0) < 0$, tak se banka zadlužila musíme tuto hodnotu započítat do celkové časové složitosti všech operací. 

    Mohlo se stát, že jsme na začátku nezačínali s prázdnou datovou strukturou, ale už jsme ji přebrali odjinud. V takovém případě potřebujeme na začátku vložit na účty počáteční vklad $\Phi(D_0)$, aby fungovala pravidla pro vkládání a vybírání peněz (jinak se banka dostane do mínusu). Podobně pokud skončíme s datovou strukturou, o kterou jsme pečovali a pilně střádali penízky na budoucí drahé operace, tak nám na účtech zbyde $\Phi(D_n)$ peněz.

    Metoda potenciálu spočívá v nalezní potenciální funkce $\Phi$ a ověření, že potenciálový rozdíl $\Phi(D_{i-1})-\Phi(D_{i})$ spolu s amortizovanou složitostí operace pokryje náklady na provedení $i$-té operace.

Účetní metoda se používá i v následující variantě. Peníze rozdělíme na účty jednotlivých objektů. Operace nedostane žádné peníze, ale vždycky řekne, ze kterého účtu se bude její práce platit (většinou to jsou účty objektů, na kterých operace pracuje). Po provedení všech operací musíme ukázat, že se žádný účet nedostal do mínusu. Celková časová složitost posloupnosti operací bude odpovídat množství peněz, které jsme na začátku vložili na účty.

Amortizovanou složitost nemusíme počítat jen pro operace, ale i pro řádky zdrojového kódu, které se provádí několikrát. Například pro řádky v cyklu nebo v několika do sebe vnořených cyklech. Protože časová složitost vybraných řádek může být proměnlivá, tak nepočítáme celkovou časovou složitost podle počtu do sebe vnořených cyklů, ale přes účty. Díky tomu se nám často podaří ukázat lepší odhad.

V následujících podsekcích si na ukážeme výpočet amortizované časové složitosti pomocí všech tří metod na příkladech.

Kavárna “U Zavěšeného kafe”

V Praze je kavárna “U Zavěšeného kafe”. Na jedné zdi v kavárně visí několik hrnečků. Někteří hosté se mohou projevit jako dobrodinci. Když platí stovkou nebo jinou papírovou bankovkou, tak řeknou: “To je dobrý, nic mi nevracejte. Zbytek dejte do toho hrnku za zdi.” A když do kavárny přijde nějaký chudý student, tak může barmana poprosit, jestli si může dát kafe na účet toho hrnku na zdi. Pokud je v hrnku dostatek peněz, tak dostane kafe.

Amortizovaná cena jednoho kafe je přesně tolik, kolik si účtuje kavárna. Ale jeho reálná cena je pro každého jiná. Bohatí dobrodinci vydají ze své peněženky za kafe víc. Normální lidé platí tolik, kolik kafe stojí a chudí studenti platí méně, protože část ceny hradí z hrnku na zdi.

Nafukovací pole

Potřebujeme navrhnout funkci $pridej(x)$, která do pole přidá prvek $x$.

Pokud dopředu nevíme, jak velké pole budeme potřebovat, tak začneme s malým polem velikosti jedna2 a v případě potřeby ho zvětšíme. Vždy, když se nám přidávaná položka nevejde do aktuálního pole, tak vytvoříme nové pole o dvojnásobné velikosti. Všechny položky do něj zkopírujeme, staré pole zrušíme a $x$ přidáme až do nového pole. Vytvoření nového pole, kopírování prvků a rušení starého pole dohromady zabere čas $tn=\OO(n)$, kde $n$ je velikost starého pole a $t$ je nějaká konstanta. Tolik je i časová složitost operace $pridej$ v nejhorším případě. Časová složitost operace $pridej$ je v nejhorším případě výrazně větší než v obyčejném poli, kde přidání prvku trvá jen $\OO(1)$.

Ve skutečnosti to není tak zlé, protože časově náročné vytváření nového pole nastává málo často. Pokud jsme právě vytvořili nové pole o $2n$ položkách, tak musíme přidat dalších $n$ čísel, než se pole zaplní a bude ho potřeba znova nafouknout.

Pro přidání $n$ čísel do prázdného pole musíme provést nafukování celkem $k$-krát, kde $k=\lfloor \log n \rfloor$. Jedno nafouknutí pole $n$ čísel trvá čas $tn$. Celkový čas všech nafukování je $t(1+2+4+8+\dots+2^{k-1}) = t\cdot 2^k \leq 2tn$. Dohromady s časem za samotné přidání prvků do pole dostáváme amortizovanou složitost jedné operace $(2t+1)n/n=2t+1=\OO(1)$.

Druhá možnost výpočtu amortizované složitosti je pomocí účetní metody. Na začátku dáme každé operaci $pridej$ $(2t+1)$ korun a každému políčku v poli otevřeme účet. Operace zaplatí jednu korunu za vlastní přidání prvku do pole a zbylých $2t$ korun dá na účet aktuálního políčka. Pokud se pole velikosti $k$ zaplní, znamená to, že jsme od posledního nafouknutí přidali dalších $k/2$ prvků. Na účtě tedy máme $tk$ korun, které použijeme na vytvoření nového pole a zkopírování všech $k$ prvků.

Podobně můžeme počítat i pomocí metody potenciálu. Za potenciál můžeme zvolit $\Phi = 2t\cdot \mbox{\#prvků v poli}$.

Přičítání jedničky

V čítači máme hodně dlouhé binární číslo $x$ a postupně k němu přičítáme jedničku. Číslo $x$ má $n$ bitů a jeho bity jsou uloženy v poli $\ARRAY{A}{\cdot}$. Nejnižší bit je uložen v $\ARRAY{A}{0}$ a nejvyšší bit v $\ARRAY{A}{n-1}$, takže $x=\sum_{i=0}^{n-1} \ARRAY{A}{i}\cdot 2^i$.

Přičítání děláme tak, jak nás to učili na základní škole. Zkusíme přičíst jedničku k poslednímu bitu. Pokud je nultý bit nula, tak jej přepíšeme na jedničku a jsme hotoví. Pokud je nultý bit jednička, tak obě jedničky sečteme a dostaneme “10”, zapíšeme nulu a jedničku přeneseme o bit výše. Tam ji přičítáme k prvnímu bitu úplně stejně, jako jsme to dělali u nultého bitu. Pokud dojde k dalšímu přenosu, tak pokračujeme analogicky. Práci na úrovni jednoho bitu označíme za jeden krok.

Jak dlouho bude trvat přičtení jedničky? To záleží na aktuálním čísle v čítači. Pokud bude na konci nula, tak jsme po jednom kroku hotoví. Ale pokud bude na konci čísla $k$ jedniček, tak budeme muset provést $k+1$ kroků. V nejhorším případě bude přičtení jedničky trvat $\OO(n)$.

Jak dlouho bude trvat přičtení $m$ jedniček? Předpokládejme, že je čítač na začátku vynulován. V každém druhém přičtení je poslední bit čítače nula (v čítači je sudé číslo) a proto bude přičítání trvat jen jeden krok. Tuto úvahu můžeme zobecnit. Pokud dojde k přenosu na $k$-tém bitu, tak muselo dojít i k přenosu na všech nižších bitech a tím pádem jsou všechny nižší bity vynulovány. Aby se na pozici $k$-tého bitu dostala opět jednička, budeme muset aspoň $2^k$ krát přičíst jedničku.

Proto můžeme říci, že krok na úrovni nultého bitu proběhne pokaždé, krok na úrovni prvního bitu jen při každém druhém přičtení, krok na úrovni třetího bitu jen při každém čtvrtém přičtení a tak dále. Celkem tedy proběhne $m+ m/2 + m/2^2 + m/2^3 + \dots + m/2^{l} \leq 2m $ kroků, kde $l=\lfloor\log m\rfloor$ (použili jsme vzorec pro součet geometrické řady $1+1/2+1/4+1/8+\dots = 2$). Z toho dostáváme amortizovanou časovou složitost jednoho přičtení $2m/m=2$.

Druhou možností, jak určit amortizovanou časovou složitost, je použití účetní metody. Každému bitu otevřeme účet. Po celou dobu bude platit, že hodnota bitu udává počet korun, které má na účtě. Začneme s vynulovaným čítačem. Každá operace přičtení jedničky dostane dvě koruny. Jednu použije na první krok a druhou vloží na účet nultého bitu. Pokud by při tomto přičítání došlo k přenosu, tak jsou na účtu nultého bitu dvě koruny. Ty vybereme, dáme je přenášené jedničce a nultý bit nastavíme na nulu. Přenášená jednička má zase dvě koruny a může je na úrovni vyššího bitu použít úplně stejně. Tímto způsobem je každá operace přičtení schopna zaplatit za svoji práci. Proto je amortizovaná složitost jedné operace přičtení jedničky dva.

Pokud na začátku nezačínáme s prázdným čítačem, tak musíme každé jedničce v čítači vložit na účet jednu korunu. Zbytek už proběhne stejně.

Třetí možnost výpočtu amortizované složitosti je přes potenciál. Za potenciál $\Phi(i)$ zvolíme počet jedničkových bitů binárního čísla (po přičtení $i$ jedniček). To, že potenciál funguje, se ukáže stejně jako u účetní metody.

Počítání stupňů vrcholů

Dostaneme graf s vrcholy $\{1,2,\dots, n\}$ a $m$ hranami reprezentovaný seznamem sousedů,3 tj. pro každý vrchol dostaneme spojový seznam sousedních vrcholů. V tomto grafu bychom chtěli pro každý vrchol spočítat jeho stupeň.4 Můžeme postupovat podle následujícího algoritmu.

for $v=1$ to  $n$  do
	$deg[v]:=0$
	for all $w\in { sousedi[v]}$     do
		 $deg[v]:=deg[v]+1$

Jaká je časová složitost tohoto algoritmu? Mohli byste říci, že se algoritmus skládá ze dvou for-cyklů, každý for-cyklus proběhne nejvýše $n$-krát a proto bude časová složitost algoritmu $\OO(n^2)$. Ale ono se dá ukázat, že časová složitost je jen $\OO(n+m)$.

K výpočtu amortizované časové složitosti použijeme variantu účetní metody. Za operace budeme považovat jednotlivé řádky algoritmu. Každému vrcholu grafu a každé hraně otevřeme v bance účet. Řádku $2$ a průběh prvním for-cyklem budeme účtovat aktuálnímu vrcholu $v$. Řádku $4$ a průběh druhým for-cyklem budeme účtovat hraně $vw$.

Po skončení algoritmu jsme z účtů zaplatili všechnu práci, kterou algoritmus vykonal. Každému vrcholu jsme z účtu strhli jen $2$ koruny za provedení řádek $1$ a $2$. Každé hraně jsme strhli $2+2$ koruny za provedení řádek $3$ a $4$ dvakrát (na hranu jsme se podívali z každého koncového vrcholu jednou). Celkem jsme zaplatili $2n+4m=\OO(n+m)$ korun.