Složitost

Complexity of Problems and Algorithms

Amortized Complexity

Složitost problému

Je zdola ohraničená dokazovaním a zhora ohraničená složitostí konkrétního algoritmu, který problém řeší.

Amortizovaná složitost

Nejhorší složitost posloupnosti operací na dané datové struktuře.

Aggregační metoda

Hrubou silou sečti složitosti jednotlivých operací v posloupnosti.

$c_{i}$ je opravdová složitost $i$ -té operace.
$\overset{c_{i}}{^}$ je počet "kreditů", které $i$ -tá operace stojí.
Pokud $\overset{c_{i}}{^} > c_{i}$ , pak ukládáme kredity "do zásoby".
Pokud $\overset{c_{i}}{^} < c_{i}$ , musíme doplatit rozdíl kredity, které jsme si dali do zásoby dříve.
Před první operací je v zásobě 0 kreditů: $D_{0} = 0$ .
Kreditový invariant: V kreditové zásobě $D_{i}$ musí být vždy nezáporný počet kreditů: $\sum_{i = 1} \overset{c_{i}}{^} - \sum_{i = 1} c_{i} \geq 0$ .
Amortizovaná složitost libovolné posloupnosti operací je nejvýše součet kreditové hodnoty každé z operací.

Vymysli potenciálovou funkci $Φ (D_{i})$ , která každé datové struktuře, jenž může vzniknout některou z operací, přiřadí reálné číslo.
Musí platit $Φ (D_{0}) = 0$ a $Φ (D_{i}) \geq 0$ .
$c_{i}$ je opravdová složitost $i$ -té operace.
$\overset{c_{i}}{^} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})$ je amortizovaná složitost $i$ -té operace.
Složitost libovolné posloupnosti operací je nejvýše součet amortizovaných složitostí jednotlivých operací.