Dynamizace - Dynamization

v počítačová věda, dynamizace je proces transformace a statická datová struktura do dynamický jeden. Ačkoli statické datové struktury mohou poskytovat velmi dobrou funkčnost a rychlé dotazy, jejich užitečnost je omezena kvůli jejich neschopnosti rychle růst / zmenšit se, což je činí nepoužitelnými pro řešení dynamické problémy, kde se mění množství vstupních dat. Dynamizační techniky poskytují jednotné způsoby vytváření dynamických datových struktur.

Problémy s rozložitelným vyhledáváním

Definujeme problém ${displaystyle P}$ hledání predikátu ${displaystyle M}$ zápas v sadě ${displaystyle S}$ tak jako ${displaystyle P (M, S)}$ . Problém ${displaystyle P}$ je rozložitelný pokud je sada ${displaystyle S}$ lze rozložit na podmnožiny ${displaystyle S_ {i}}$ a existuje operace ${displaystyle +}$ sjednocení výsledku tak, že ${displaystyle P (M, S) = P (M, S_ {0}) + P (M, S_ {1}) + tečky + P (M, S_ {n})}$ .

Rozklad

Dekompozice je termín používaný v informatice k rozdělení statických datových struktur na menší jednotky nestejné velikosti. Základním principem je myšlenka, že jakékoli desetinné číslo lze převést na reprezentaci v jakékoli jiné základně. Další podrobnosti o tématu viz Dekompozice (informatika). Pro zjednodušení bude v tomto článku použit binární systém, ale jakákoli jiná základna (stejně jako další možnosti, jako je Fibonacciho čísla ) lze také použít.

Pokud používáte binární systém, sada ${displaystyle n}$ prvky jsou rozděleny do podskupin velikostí s

{displaystyle 2 ^ {i} * n_ {i}}

prvky kde ${displaystyle n_ {i}}$ je ${displaystyle i}$ -tý kousek ${displaystyle n}$ v binárním formátu. To znamená, že pokud ${displaystyle n}$ má ${displaystyle i}$ -tý bit rovný 0, odpovídající sada neobsahuje žádné prvky. Každá z podmnožiny má stejnou vlastnost jako původní struktura statických dat. Operace prováděné s novou dynamickou datovou strukturou mohou zahrnovat procházení ${displaystyle log _ {2} vlevo (noc)}$ množiny tvořené rozkladem. Výsledkem bude přidání ${displaystyle O (přihlásit vlevo (noc))}$ faktor na rozdíl od operací statické datové struktury, ale umožní přidání operace vložení / odstranění.

Kurt Mehlhorn prokázal několik rovnic pro časovou složitost operací na datových strukturách dynamizovaných podle této myšlenky. Některé z těchto rovností jsou uvedeny.

Li

 ${displaystyle P_ {S} vlevo (noc) ,!}$  = čas na vytvoření statické datové struktury ${displaystyle Q_ {S} vlevo (noc) ,!}$  = čas na dotaz na statickou datovou strukturu ${displaystyle Q_ {D} vlevo (noc) ,!}$  = čas dotazu na dynamickou datovou strukturu tvořenou rozkladem ${displaystyle {overline {I}}}$  = amortizovaná doba vložení

pak

  ${displaystyle Q_ {D} left (night) = O (Q_ {S} left (night) log left (night)) ,!}$   ${displaystyle {overline {I}} = O (vlevo (P_ {S} vlevo (noc) / noc) přihlásit vlevo (noc))}$

Li ${displaystyle Q_ {S} vlevo (noc)}$ je alespoň polynomiální, pak ${displaystyle Q_ {D} vlevo (noc) = Oleft (Q_ {S} vlevo (noc) noc)}$ .

Další čtení

Kurt Mehlhorn, Datové struktury a algoritmy 3,. Série EATCS, sv. 3, Springer, 1984.