---
title: Amortizovaná složitost
tags: cvičení
description: View the slide with "Slide Mode".
---

# B-stromy preemptivní insert
B-strom = $(a,2a)$-strom

vizualizace https://www.cs.usfca.edu/~galles/visualization/BTree.html

---

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

1. $11110001010101010011\color{red}{0} + 1 = 11110001010101010011\color{red}{1}$ : 1 krok
2. $1111000101\color{red}{01111111111} + 1 = 1111000101\color{red}{10000000000}$ : $11$ kroků = $O(\log n)$

případ 2. se provede jen občas.

# agregačmí metoda

$n\times$ přičteme 1 k 0:

${0000}$
$\color{red}{0001}$
$\color{blue}{0010}$
$\color{red}{0011}$
$\color{green}{0100}$
$\color{red}{0101}$
$\color{blue}{0110}$
$\color{red}{0111}$
$\color{lime}{1000}$
$\color{red}{1001}$
$\color{blue}{1010}$
$\color{red}{1011}$
$\color{green}{1100}$
$\color{red}{1101}$
$\color{blue}{1110}$
$\color{red}{1111}$

<span style="color:red">Pro $n$ přičtení se mění poslední pozice</span>
<span style="color:blue">pro $n/2$ přičtení se mění předposlední pozice</span>
<span style="color:green">pro $n/4$ přičtení se mění 3. pozice od konce</span>
<span style="color:lime">...</span>

počet operací pro $n$ přičtení=$\sum_1^{\log n} \frac{n}{2^i}=n\sum_1^{\log n} \frac{1}{2^i}<=n\sum_1^{\infty} \frac{1}{2^ i}=2n$
Takže na jednu operaci je $O(1)$

---

# penízková metoda
každá jedničkka mě stojí 1 operaci za vložení a přidá mi "penízek" za přidání. Ten "utratím" při přenosu.

$\color{orange}{1111}000\color{orange}{111}0\color{orange}{1}0\color{orange}{1}0\color{orange}{1}00\color{orange}{111} + 1 = \color{orange}{1111}000\color{orange}{111}0\color{orange}{1}0\color{orange}{1}0\color{orange}{1}0\color{orange}{1}000$

---

# potenciálová metoda??

operace $o_1,\ldots,o_n$ s reálnou cenou $C_1,\ldots,C_N$ a amortizovaná cena $A_1,\ldots,A_N$.
Potenciál $\Phi_0\geq 0$. A po provedení prvních $i$ operací $\Phi_i=\sum_{j\leq i} A_j - \sum_{j\leq i} C_j$
Potenciálový rozdíl $\Delta\Phi_i=\Phi_i-\Phi_{i-1}=A_i-C_i$
Pokud $\Delta\Phi_i<0$ čas spotřebuje. (při přenosu všechny penízky utratím)
Pokud $\Delta\Phi_i>0$ čas ukládá.(1 vloží penízek)

Potenciál $\Phi_i$=počet jedniček v binárním zápisu čísla (vždy větší než 0). Takže pro každé $0\leq i \leq n; i\geq 0$.
1. $\Delta\Phi_i=1$ pokud je na konci čísla 0, takže jsem si "naspořil jednu k dobru" a amortizovaná cena $A_i=C_i+\Delta\Phi_i=1+1=2$.
2. $\Delta\Phi_i=-j+1$ kde $j>0$ je počet 1 na koci čísla, takže "utrácím". Skutečná cena $C_i=j+1$ (počet jedniček na konci čísla$+1$, zápis přenosu) a tedy $A_i=C_i+\Delta\Phi_i=-j+1 + j+1=2$

Průběh potenciálu: