{{TOC float}}
{{Sources|
''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 Popisu K. Mehlhorna v knize '''Algorithms and Complexity vol. 1 J. Van Leeuwena''' (viz Google Books). -- [[User:Tuetschek|Tuetschek]] 00:16, 21 Aug 2010 (CEST). Martin Mares ma k tomu hezke PDFko [http://mj.ucw.cz/vyuka/1516/ds2/06-trans.pdf]''
}}
==Úvod==
Mnoho datových struktur podporuje velice efektivní operaci '''MEMBER''', ale nemá operace '''INSERT''' a '''DELETE''' (např. uspořádané pole). Ú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> -- pro prvek a nějakou množinu vrací nějakou hodnotu (níže nazýváme VYCIS).
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>. V praxi naši S-strukturu postavíme pro dané A, provádíme nad ní VYCIS, celou smažeme, postavíme pro nové A, pořád dokola. Nic jiného s ní dělat nelze.
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 '''VYCIS'''. 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 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 (z S-struktury nemusíme umět číst prvky, proto je radši evidujeme "vedle" ve spojáku), a nakonec pomocnou dynamickou strukturu <math>T\,\!</math> (např. binární vyhledávací strom). 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>).
Struktura <math>T\,\!</math> 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 v popisech operací vynecháme.
Pokud by náš vyhledávací problém <math>f(x,A)</math> realizoval problém MEMBER (náležení prvku do množiny), již pro něj existují efektivnější řešení, než semidynamizace. Představme si raději složitější vyhledávací problém, např. eukleidovská vzdálenost prvku od množiny.
===Operace VYCIS===
Operace '''VYCIS''' potom projde všechny neprázdné množiny <math>A_i\,\!</math> a zavolá '''VYCIS''' na nich. Výsledeky spojí za pomoci funkce <math>\circ\,\!</math>.
To celkem dává složitost '''VYCIS'''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>Q_{\mathcal{S}} = n^{\epsilon}\,\!</math> pro nějaké <math>\epsilon > 0\,\!</math>, pak je operace '''VYCIS''' <math>O(n^{\epsilon})\,\!</math>.
===Operace INSERT===
Operace '''INSERT''' najde nejmenší <math>i\,\!</math> takové, že <math>A_i=\emptyset\,\!</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 z prvků výsledného spojáku 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>. Zároveň se prvek přidá do T.
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|1}}:
:<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 '''VYCIS''' 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''' rychlý amortizovaně, 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\geq 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\,\!</math>, t.ž. <math>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| \leq 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^j\,\!</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|\leq 2^j\,\!</math>, jinak by pro <math>j\,\!</math> nebylo nejmenší.
# Položíme <math>A_i = \emptyset\,\!</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|2}}
# 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|\leq 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.
----
{{note|1|Protože čas vyhledání prvku ve struktuře <math>T\,\!</math> je logaritmický a tady pracujeme s většími čísly, můžeme ho tu zanedbat.}}
{{note|2|Díky pomocné datové struktuře <math>T\,\!</math>to lze udělat rychle -- rychle zjistíme, kde se <math>x\,\!</math> nachází.}}
{{Statnice I3}}
