4.6 Amortizovaná časová složitost

Složitost operací nad dynamickými množinami dat

Binární minimová halda je příklad dynamické množiny dat, jejíž velikost i konkrétní složení se v závislosti na posloupnosti operací HeapInsert a HeapExtractMin průběžně mění.
Složitost operace vložení či odebrání prvku takové struktury v nejhorším nebo v nejlepším případě nevystihuje vždy nejlépe skutečné chování algoritmu takové operace v rámci životního cyklu takové datové struktury.
Proto je u algoritmů nebo operací, které se volají mnohokrát nad dynamicky se měnící datovou strukturou, užitečné stanovit tzv. amortizovanou složitost\(^1\).

\(^1\)Naše definice zde je jen pro „zvětšující se“ datové struktury. Preciznější definici zavedeme v BI-AG2.

Definice 4.4 (Amortizovaná časová složitost)

Amortizovaná časová složitost

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í.

Pro odhad časové složitosti jednotlivých provedení takové operace se stále bere nejhorší případ.
Amortizovanou složitost je třeba stanovovat přes dostatečně dlouhé posloupnosti operací. Typický kontext amortizované analýzy je sekvence všech operací od inicializace datové struktury do vybudování struktury velikosti \(n\).
Složitost jednoho konkrétního volání operace v nejhorším případě může být řádově větší.

Problém nafukovacího pole

Popíšeme si nyní strategii vybudování dynamického 1D pole o velikosti \(n\) postupným přidáváním jednotlivých nových prvků tak, že celková časová složitost bude pouze \(O(n)\) a tedy přidání jednoho prvku má amortizovanou složitost \(O^∗(1)\).

Vstup

Na vstup přicházejí průběžně datové prvky, které je potřeba ukládat do pole \(P[1,...]\), \(i\)-tý prvek na index \(i\).

Problém

Navrhněte operaci NPInsert, která vkládá prvky do pole, když
- jejich celkový počet \(n\) předem neznáme a ani ho nedokážeme rozumně odhadnout,
- a tudíž nelze předem alokovat dostatečně velké pole,
- a na počátku alokujeme pole minimální velikosti \(m_0 = 1\).

Idea

Počáteční kapacitu pole \(P\) zvolíme \(m_0 = 1\)
Označme momentální kapacitu pole \(P\) v prvcích jako \(m\)
Předpokládejme, že počet aktuálně uložených prvků v \(P\) je \(i − 1\) a že chceme vložit \(i\)-tý prvek.
Jestliže \(i \le m\), pak prvek vložíme na volnou pozici \(i\).
Jestliže \(i \gt m\), pak je v \(P\) uloženo \(m\) prvků (došla volná místa) a tudíž:
- přealokujeme \(P\) na velikost \(2m\) prvků
- do první poloviny nakopírujeme staré pole
- následně staré pole zrušíme,
- nový prvek vložíme na index \(m + 1\).

Algoritmus

Algoritmus NPInsert(P, x):

    Nechť i je pořadové číslo vkládaného prvku od začátku vkládání.
    Pokud i ≤ m: P[i] := x; i := i + 1; return
    Pokud i > m
        Alokuj pole P′ o velikosti 2m
        Překopíruj P do první poloviny pole P′
        Dealokuj P; P := P′
        P[i] := x; i := i + 1

Časová složitost

Časová složitost volání NPInsert na pole s \(i\) prvky je v nejhorším případě \(\Theta(i)\).

Věta 4.6 (O amortizované analýze nafukovacího pole)

O amortizované analýze nafukovacího pole

Uvažujme na počátku prázdné nafukovací pole. Potom celková časová složitost posloupnosti \(n\) operací NPInsert je \(\Theta(n)\), neboli amortizovaná složitost operace NPInsert je \(\Theta^*(1)\).

Důkaz Věty 4.6

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 \(\Theta(n)\).
Případné zvětšování při vložení \(i\)-tého prvku trvá čas \(\Theta(i)\)
Ke zvětšování dochází právě tehdy, když \(i\) je mocnina dvou.
Všechna zvětšení tedy dohromady stojí \(\Theta(2^{0} + 2^{1} + ··· + 2^{k}),\) kde \(2^{k}\) je nejvyšší mocnina dvojky menší než \(n\).
V závorce je geometrická posloupnost se součtem \(2^{k+1} − 1 \lt 2n\)
Celková časová složitost proto činí \(\Theta(n)\).

K Zamyšlení

Jak závisí tvrzení předchozí věty na volbě počáteční kapacity \(m_0\)?
Jak by se amortizovaná složitost změnila, pokud bychom zvolili jinou strategii nafukování pole? Například, pokud by velikost nového většího pole nebyla volena jako dvojnásobná, ale
(a) jako trojnásobná,
(b) větší o nějakou pevnou konstantu \(c\) a \(m_0 = c\).
Uvažujme na počátku prázdnou binární haldu \(H\) a posloupnost \(n\) operací HeapInsert(\(H,...\)). Vypočítejte amortizovanou složitost operace HeapInsert.

Věta 4.7 (o složitosti HeapBuild)

Věta o amortizované analýze nafukovacího pole

Operace HeapBuild má časovou složitost \(O(n)\)

Důkaz Věty 4.7

Na každý vrchol na začátku položíme p penízků. Co dělá každý prvek?

Porovná se s menším ze synů (2 instrukce), může se s menším prohodit (1 instrukce) a pak se případně probublává dolů (směrem k listu).
Ukážeme, že za toto zvládne „zaplatit“ jeden z podstromů.
Když tedy nakonec přesuneme všechny zbylé penízky do kořene aktuálního stromečku, zbyde nám alespoň \(p · (k + 1)\) penízků, kde \(k\) je vzdálenost kořenu uvažovaného stromečku od listů.

Důkaz proběhne indukcí podle \(k\) – vzdálenosti od listu. (Pro jednoduchost předpokládáme, že poslední hladina je zcela zaplněná – tím formálně ukazujeme \(2pn\), ale není těžké důkaz poupravit.)

ZI: \(k = 0\). Triviálně platí, neboť neprovedeme žádné porovnání a na kontě zůstane \(p = p(k + 1)\).
IK: \(k - 1 \Rightarrow k\). Máme „nový kořen“ ve stromě \(T\) a předpokládáme, že podstromy \(T_{ℓ}\) a \(T_{r}\) jsou korektně vytvořeny a že (IP) každý z jejich kořenů má na kontě \(pk\). Hloubka stromu \(T\) je \(k + 1\). Všimli jsem si, že v nejhorším případě uděláme s novým prvkem na každé hladině (krom poslední) \(3\) operace. Celkově tedy za „opravení“ stromu \(T\) zaplatíme \(3k\). Na konci nám tedy zbyde \(z = p + 2pk − 3k\). Pokud zvolíme \(p \geq 3\), bude jistě \(z \geq p(k + 1)\)