Příklady 6. 10. 2021
Z přednášky umíme vytvořit natahovací pole, kterému \(n\) vložení na konec (začínaje s
prázdným polem) trvá \( \mathcal{O}(n) \). Tedy amortizovaně konstantní složitost na
přidání. (Ano, je v pořádku, že ještě nevíte, co znamená to "amortizovaně" :-))
K tomu jsme použili techniku zdvojování (doubling): Kdykoliv je pole plné, tak ho
realokujeme do nového pole, které má dvojnásobnou kapacitu.
Př. 1: Natahujeme pole
Co by se stalo, kdybychom zvyšovali kapacitu jinak, než na dvojnásobek? Uvažte
následující možnosti (\(C\) je původní kapacita):
- \(C \rightarrow C + k\), \(k\) je konstanta (pro začátek 1)
- \(C \rightarrow C^2\)
- \(C \rightarrow 3\cdot C\), nebo obecně \(C \rightarrow k\cdot C\) pro nějakou
konstantu \(k > 1\)
Př. 2: Smršťujeme pole
Do teď jsme přidávali nové prvky jen na konec pole. Šlo by konstrukci upravit tak,
abychom mohli přidávat i na začátek (při zachování složitosti)? A co kdybychom chtěli
prvky z konce (začátku) i mazat?
Př. 3: Binární počítadlo
Analyzujte složitost binárního počítadla. Binární počítadlo se skládá z jednoho
binárního čísla (s potenciálně libovolným počtem cifer) a umí jedinou operaci "přičti
jedničku". Počítadlo začíná nastavené na nulu (všechny cifry jsou nastaveny na nulu) a
složitost počítáme jako počet operací "přečti cifru" a "změň cifru".
Jakou celkovou složitost bude mít \(n\) operací na počítadle, začínaje s vynulovaným
počítadlem? A co kdybychom chtěli podporovat i operaci "odečti jedničku"? Dalo by se
počítadlo upravit tak, aby složitost zůstala stejná?