Dynamizace - Dynamization

Ve výpočetní technice je dynamizace procesem transformace statické datové struktury na dynamickou . 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ých problémů , 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 hledání predikátové shody v množině jako . Problém je rozložitelný, pokud lze sadu rozložit na podmnožiny a existuje operace sjednocení výsledku taková . ${\ displaystyle P}$${\ displaystyle M}$${\ displaystyle S}$${\ displaystyle P (M, S)}$${\ displaystyle P}$${\ displaystyle S}$${\ displaystyle S_ {i}}$${\ displaystyle +}$${\ 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ší informace o tématu naleznete v části Dekompozice (informatika) . Pro zjednodušení bude v tomto článku použit binární systém, ale lze také použít jakoukoli jinou základnu (stejně jako další možnosti, jako jsou Fibonacciho čísla ).

Pokud používáte binární systém, sada prvků je rozdělena do podskupin velikostí s ${\ displaystyle n}$

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

prvky, kde je -tý bit v binární podobě. To znamená, že pokud má -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é na nové dynamické datové struktuře mohou zahrnovat procházení sad vytvořených rozkladem. Ve výsledku to přidá faktor oproti operacím statické datové struktury, ale umožní přidání operace vložení / odstranění. ${\ displaystyle n_ {i}}$${\ displaystyle i}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle i}$${\ displaystyle \ log _ {2} \ left (n \ right)}$${\ displaystyle O (\ log \ left (n \ right))}$

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}\left(n\right)\,\!}$ = time to build the static data structure
${\displaystyle Q_{S}\left(n\right)\,\!}$ = time to query the static data structure
${\displaystyle Q_{D}\left(n\right)\,\!}$ = time to query the dynamic data structure formed by decomposition
${\displaystyle {\overline {I}}}$ = amortized insertion time

pak

 ${\displaystyle Q_{D}\left(n\right)=O(Q_{S}\left(n\right)\log \left(n\right))\,\!}$
 ${\displaystyle {\overline {I}}=O(\left(P_{S}\left(n\right)/n\right)\log \left(n\right))}$

Pokud je alespoň polynom , pak . ${\ displaystyle Q_ {S} \ vlevo (n \ vpravo)}$${\ displaystyle Q_ {D} \ left (n \ right) = O \ left (Q_ {S} \ left (n \ right) \ right)}$

Další čtení

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