{{TOC float}}
''Tento popis byl původně vytvořen podle [http://ktiml.mff.cuni.cz/teaching/files/materials/dsii2.pdf Koubkových skript], [[TIN066 Skripta Vidner-Kotal|skript Vidner-Kotal]] a [http://www.google.com/books?hl=cs&lr=&id=-X39_rA3VSQC&oi=fnd&pg=PA326#v=onepage&q&f=false popisu K. Mehlhorna]. -- [[User:Tuetschek|Tuetschek]] 00:16, 21 Aug 2010 (CEST)''
==Úvod==
Mnoho datových struktur podporuje velice efektivní operaci '''MEMBER''', ale nemá operace '''INSERT''' a '''DELETE'''. Úkolem ''dynamizace'' je právě tyto operace do jakékoliv obecné struktury co nejefektivněji doplnit.
===Zobecněný vyhledávací problém===
''Zobecněný vyhledávací problém'' je libovolná funkce <math>f:U_1\times 2^{U_2} \to U_3\,\;</math> -- dostává prvek a nějakou množinu a vrací (libovolnou hodnotu).
Struktura <math>\mathcal{S}\,\;</math> je ''statická struktura řešící vyhledávací problém'' (neboli ''S-struktura'') <math>f\,\;</math>, je-li dán algoritmus, který pro <math>A\subseteq U_2\,\;</math> zkonstruuje datovou strukturu <math>\mathcal{S}(A)\,\;</math> a algoritmus, který pro <math>x\in U_1\,\;</math> a <math>\mathcal{S}(A)\,\;</math> spočte <math>f(x,A)\,\;</math>.
Struktura je ''[[#Semidynamizace|semidynamická]]'', pokud navíc existuje algoritmus, který pro <math>x\in U_2\,\;</math> a <math>\mathcal{S}(A)\,\;</math> zkonstruuje S-strukturu <math>\mathcal{S}(A\cup\{x\})\,\;</math>.
Struktura je ''[[#Dynamizace|dynamická]]'', pokud navíc existuje algoritmus, který pro <math>x\in A\,\;</math> a <math>\mathcal{S}(A)\,\;</math> zkonstruuje S-strukturu <math>\mathcal{S}(A\backslash\{x\})\,\;</math>.
Ve všech následujících operacích budeme uvažovat jen ''rozložitelný'' vyhledávací problém:
* Vyhledávací problém je ''rozložitelný'', pokud existuje binární operace <math>\circ\,\;</math> na univerzu <math>U_3\,\;</math> taková, že pro disjunktní <math>A,B\subseteq U_2\,\;</math> a <math>x\in U_1\,\;</math> platí <math>f(x,A)\circ f(x,B) = f(x,A\cup B)\,\;</math>.
To platí pro situaci, která nás nejvíc zajímá -- pokud funkce <math>f\,\;</math> provádí operaci '''MEMBER''' nad nějakou datovou strukturou. Jiné problémy (patří <math>x\,\;</math> do konvexního obalu množiny?) ale rozložitelné nejsou.
Navíc budeme předpokládat, že funkce <math>\circ\,\;</math> lze spočítat v konstantním čase. Označme
* <math>Q_{\mathcal{S}}(n)\,\;</math> čas na vyčíslení <math>f(x,A)\,\;</math>, pokud <math>|A|=n\,\;</math>
* <math>S_{\mathcal{S}}(n)\,\;</math> paměťový prostor potřebný k reprezentaci <math>n\,\;</math>-prvkové množiny
* <math>P_{\mathcal{S}}(n)\,\;</math> čas na vytvoření struktury <math>\mathcal{S}(A)\,\;</math> pro <math>|A|=n\,\;</math>
Pro asymptotické odhady budeme předpokládat, že funkce <math>Q_{\mathcal{S}}(n)\,\;</math>, <math>\frac{S_{\mathcal{S}}(n)}{n}\,\;</math> a <math>\frac{P_{\mathcal{S}}(n)}{n}\,\;</math> jsou neklesající.
==Semidynamizace==
Vytvoříme semidynamickou strukturu, jejíž čas operace '''INSERT''' bude velmi rychlý a navíc se nám moc nepokazí doba pro provedení operace '''MEMBER'''. Základní idea je podobná jako v binomiálních haldách -- roztrháme reprezentovanou množinu <math>A\,\;</math> na sadu ''disjunktních'' podmnožin <math>A_i</math> o velikosti <math>2^i\,\;</math> (takové množiny jsou neprázdné pro <math>i\,\;</math> odpovídající jedničkám v binárním zápisu čísla <math>|A|\,\;</math>.
Formálně budeme mít spojový seznam S-struktur <math>\mathcal{S}(A_i)\,\;</math> odpovídajících množinám <math>A_i\,\;</math>, potom seznam spojových seznamů <math>s(A_i)\,\;</math>, které obsahují prvky jednotlivých množin, a nakonec pomocnou dynamickou strukturu <math>T\,\;</math> (např. binární vyhledávací strom)<ref>Tahle struktura se používá k "rychlému" testování před '''INSERT'''em, zda nechceme vkládat prvek, který už v množině máme, případně před '''DELETEM''', jestli nechceme mazat neexistující prvek. Pro jednoduchost to vynecháme, ale je dobré o té struktuře vědět.</ref>. To všechno dohromady zjevně vyžaduje jen <math>O(S_{\mathcal{S}}(n))\,\;</math> paměti (celkem reprezentujeme pořád stejně prvků a vyhledávací stromy i spojáky jsou <math>O(n)\,\;</math>).
===Operace MEMBER===
Operace '''MEMBER''' potom projde všechny neprázdné množiny <math>A_i\,\;</math> a zavolá '''MEMBER''' na nich. Výsledek spojí za pomoci funkce <math>\circ\,\;</math>.
To celkem dává složitost '''MEMBER'''u <math>O(Q_{\mathcal{S}}(n)\log(n))\,\;</math>, protože hledáme v max. <math>\log_2\,\;</math> dílčích množinách.
Protože jakékoliv mocniny rostou rychleji než logaritmus, platí, že pokud <math>P_{\mathcal{S}} = n^{\epsilon}\,\;</math> pro nějaké <math>\epsilon > 0\,\;</math>, pak je operace '''MEMBER''' <math>O(n^{\epsilon})\,\;</math>.
===Operace INSERT===
Operace '''INSERT''' najde nejmenší <math>i\,\;</math> takové, že <math>A_i=\empty\,\;</math>. Potom vezme všechny <math>A_j, j<i\,\;</math> (ty jsou neprázdné) a spolu s vkládaným prvkem je slije do jedné množiny <math>A_i\,\;</math> (zahodí S-struktury pro všechna <math>A_j, j<i\,\;</math>, zkonkatenuje spojáky <math>s(A_j)\,\;</math> a na jejich základě zkonstruuje novou S-strukturu <math>\mathcal{S}(A_i)\,\;</math>). Nová množina má správný počet prvků, protože <math>\sum_{j=0}^{i-1} 2^j + 1 = 2^i\,\;</math>.
V odhadu amortizované složitosti využijeme fakt, že S-struktura pro <math>A_i\,\;</math> se tvoří jen tehdy, když existují S-struktury pro všechny <math>A_j, j<i\,\;</math>. Tj. S-struktura o velikosti <math>2^i\,\;</math> prvků se konstruuje znovu až po dalších <math>2^{i+1}-1\,\;</math> '''INSERT'''ech. Amortizovaně tak vychází<ref>Protože čas vyhledání prvku ve struktuře T je logaritmický a tady pracujeme s většími čísly, můžeme ho tu zanedbat</ref>:
:<math>\sum_{i=0}^{\log n}\frac{P_{\mathcal{S}}(2^i)}{2^i} \leq \sum_{i=0}^{\log n}\frac{P_{\mathcal{S}}(n)}{n} = \frac{P_{\mathcal{S}}(n)}{n}\log n = O(\frac{P_{\mathcal{S}}(n)}{n}\log n)\,\;</math>.
Podobně jako pro '''MEMBER''' platí, že pokud <math>P_{\mathcal{S}} = n^{\epsilon}\,\;</math> pro nějaké <math>\epsilon > 1\,\;</math>, pak je složitost operace '''INSERT''' <math>O(n^{\epsilon-1}\,\;</math>.
===Operace INSERT se zaručeným nejhorším časem===
Protože někdy nestačí mít '''INSERT''' amortizovaně rychlý, byla vytvořena jeho varianta, která zaručuje rozumnou rychlost i v nejhorším případě. Dělá se to prostým rozložením potřebných operací do všech volání. Musíme ale povolit i požadavky na naši strukturu -- místo max. jedné množiny pro každou velikost odpovídající mocnině dvou budeme mít max. 4 takové množiny <math>A_{i,0},\dots A_{i,3}\,\;</math>, z nichž poslední navíc bývá zkonstruovaná jen částečně ("rozpracovaná").
Označme počet množin <math>A_i\,\;</math> jako <math>k_i\,\;</math>, přičemž <math>k_i = -1\,\;</math>, pokud neexistuje žádná množina velikosti <math>2^i\,\;</math>. Algoritmus potom vypadá následovně:
# Vytvoří se jednoprvková <math>A_{0,k_0+1} = \{x\}</math> a zvýší <math>k_0\,\;</math> (tj. i odpovídající S-struktura)
# Pro první souvislý úsek, kde <math>k_i\leq 0</math>:
## Provedeme dalších <math>\frac{P_{\mathcal{S}}(2^i)}{2^i}\,\;</math> konstrukce S-struktury <math>\mathcal{S}(A_i,k_i)\,\;</math>
## Pokud jsme tím tuto S-strukturu dotvořili, vezmeme první dvě struktury "o patro níž" (<math>A_{i-1,0}\,\;</math> a <math>A_{i-1,1}\,\;</math>) a připravíme je prvním krokem k sloučení. Zároveň je odtud odebereme a přečíslujeme zbylé. Jejich započaté sloučení přidáme na úroveň <math>i\,\;</math>.
# Pokud jsme v posledním kroku (<math>i,k_{i+1} = 0\,\;</math>) vytvořili druhou strukturu stejné velikosti na nejvyšším dosaženém "patře", připravíme první krok sloučení těchto dvou největších struktur, přemístíme jejich započaté sloučení "o patro výš" a odebereme původní struktury.
Díky tomu, že počet kroků volíme tak šikovně, vždycky dotvoříme strukturu právě včas na to, abychom mohli vytvářet další stejné velikosti. Navíc, protože se provede jen <math>O(\frac{P_{S}(2^i)}{2^i})\,\;</math> kroků pro každé <math>i\,\;</math>, odpovídá složitost v nejhorším případě amortizované složitosti původní operace '''INSERT'''.
==Dynamizace==
Při úplné ''dynamizaci'' navíc požadujeme efektivní algoritmus '''DELETE'''. Přidáme další předpoklad, a to, že na naší původní S-struktuře existuje operace '''FAKE-DELETE''' (ta spočívá v označení nějakého prvku jako "smazaného", aniž by se smazal skutečně -- dál tedy zabírá místo a prodlužuje operace).
Základní ideou oproti [[#Semidynamizace|semidynamizaci]] navíc je, že se budeme snažit za každou cenu zajistit, aby všechny naše pomocné S-struktury stále obsahovaly alespoň osminu "nesmazaných" prvků a přestavovat je až poté, co počet "smazaných" překročí tuto mez. Formálně naše S-struktury reprezentují vlastně množiny <math>B_i\,\;</math>, kde <math>B_i = A_i \backslash \{x_i; i=1,2\dots k\}\,\;</math> (a <math>2^{i-3} < |A_i| \geq 2^j\,\;</math>).
Asymptoticky tak zaručíme, že množin (a pomocných S-struktur) bude stále jen logaritmicky mnoho a paměťové nároky taky zůstávají asymptoticky stejné. Struktura je tedy stejná jako pro (základní) dynamizaci. Navíc jsou nyní spojové seznamy prvků přímo provázané s S-strukturami (protože už nepoznáme podle velikosti seznamu, ke které S-struktuře vlastně patří).
Operace '''MEMBER''' pak pracuje úplně stejně, jen nakonec zkontroluje, zda nalezený prvek nebyl označen jako "smazaný" (a případně ho pak nevrátí).
===Operace INSERT===
Algoritmus operace '''INSERT'''(<math>x\,\;</math>) je následující:
# Najdi nejmenší <math>j\,\;</math> takové, že <math>|\cup_{i\leq j} A_i|< 2^i\,\;</math>.
# Vytvoříme <math>A_j = \cup_{i\leq j} A_i \cup \{x\}\,\;</math> (včetně S-struktury a spojáku). To splňuje požadavky na velikost <math>2^{j-1} < |A_j|\geq 2^j\,\;</math>, jinak by pro <math>j\,\;</math> nebylo nejmenší.
# Položíme <math>A_i = \empty\,\;</math> pro <math>i<j\,\;</math>.
Díky zachovávané minimální velikosti vytvářené množiny máme složitost amortizovaně stejnou jako v případě semidynamizace.
===Operace DELETE===
Odebrání prvku <math>x\,\;</math> z naší dynamické struktury vypadá následovně:
# Odstraníme <math>x\,\;</math> ze spojáku <ref>Díky pomocné datové struktuře to lze udělat rychle -- a rychle zjistíme, kde se <math>x\,\;</math> nachází..</ref>
# Vyřešíme čtyři různé případy podle velikosti množiny <math>A_i\,\;</math>, která obsahuje prvek <math>x\,\;</math>:
## Je-li <math>A_i\,\;</math> jen jednoprvková, prostě zahodím struktury s ní spojené.
## Je-li <math>|A_i| > 2^{i-3}\,\;</math> (tj. ještě mám víc než osminu prvků "platných"), provedeme pouze '''FAKE-DELETE'''.
## Je-li <math>A_{i-1}\,\;</math> buď prázdná, nebo dost velká (<math>|A_{i-1}| > 2^{i-2}\,\;</math>), můžeme ji s <math>A_i\,\;</math> prohodit. Pro "nové" <math>A_{i-1}\,\;</math> pak vytvoříme novou S-strukturu.
## Je-li <math>A_{i-1}\,\;</math> neprázdná, ale moc malá na prohození s <math>A_{i}\,\;</math>, potom je určitě můžeme sloučit a získáme novou množinu, která splňuje velikostní omezení pro <math>A_i\,\;</math>. Pro ni vyrobíme novou S-strukturu.
Amortizovaná složitost celé operace '''DELETE''' je <math>O(D_{\mathcal{S}}(n) + \log n + \frac{P_{\mathcal{S}}(n)}{n})</math>, kde <math>D_{\mathcal{S}}(n)\,\;</math> je čas potřebný na operaci '''FAKE-DELETE''' a <math>\log n\,\;</math> je potřeba na vyhledání prvku. Odhadneme, kolikrát se dělá skutečné přestavění S-struktur. Pokud <math>x\in A_i\,\;</math>, pak '''DELETE''' může nově vytvořit jen <math>S(A_i)\,\;</math> nebo <math>S(A_{i-1})\,\;</math>. Z jejich podmínek velikosti (v algoritmu) vidíme, že mezi dvěma '''DELETE''' pro stejné <math>A_j\,\;</math> (přičemž <math>|A_j|\geq 2^{i-2}\,\;</math>) se musí provést aspoň <math>2^{j-3}\,\;</math>-krát '''FAKE-DELETE''' (a libovolný počet '''DELETE''' na jiných množinách). Amortizovaná složitost vytváření S-struktur tak vychází:
:<math>\frac{P_{\mathcal{S}}(2^{j-2})}{2^{j-3}} = O(\frac{P_{\mathcal{S}}(n)}{n})\,\;</math>
I se současně prováděnými operacemi '''DELETE''' se amortizovaná složitost operací '''INSERT''' zachovává. Aby '''INSERT''' vytvořil podruhé strukturu pro <math>A_i\,\;</math>, musí opět nastat <math>1+\sum_{j\leq i}|A_j| > 2^{j-1}\,\;</math>. Protože '''DELETE''' nikdy nevytvoří strukturu s víc než polovinou skutečně zaplněnou, musí se do té doby provést aspoň <math>2^{i-2}\,\;</math> '''INSERT'''ů, čímž získáme stejnou situaci jako u semidynamizace.
----
<references />
{{Statnice I3}}
