dynamizacja

W informatyce dynamizacja to proces przekształcania statycznej struktury danych w dynamiczną. Chociaż statyczne struktury danych mogą zapewniać bardzo dobrą funkcjonalność i szybkie zapytania, ich użyteczność jest ograniczona ze względu na ich niezdolność do szybkiego wzrostu/kurczenia się, przez co nie nadają się do rozwiązywania dynamicznych problemów, w których dane wejściowe się zmieniają . Techniki dynamizacji zapewniają jednolite sposoby tworzenia dynamicznych struktur danych.

Rozkładalne problemy wyszukiwania

Definiujemy problem ${$ dopasowania predykatu $S$ zbiorze jako $\ Displaystyle P (M,$ S $}$ Problem jest $rozkładalny$ , $jeśli$ zbiór można rozłożyć na podzbiory ${\ Displaystyle P (M, S) = P (M, S_ {0}) + P(M,S_{1})+\kropki +P(M,S_{n})}$ ujednolicenia $wyników$$,$ że .

Rozkład

Dekompozycja to termin używany w informatyce do rozbijania statycznych struktur danych na mniejsze jednostki o nierównej wielkości. Podstawową zasadą jest idea, że ​​dowolną liczbę dziesiętną można przetłumaczyć na reprezentację w dowolnej innej podstawie. Aby uzyskać więcej informacji na ten temat, zobacz Dekompozycja (informatyka) . Dla uproszczenia w tym artykule zostanie użyty system binarny, ale można również wykorzystać dowolną inną podstawę (a także inne możliwości, takie jak liczby Fibonacciego ).

W przypadku korzystania z systemu binarnego zbiór elementów jest dzielony na podzbiory rozmiarów z ${\ displaystyle n}$

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

elementy, gdzie ${\ displaystyle n_ {i}}$ jest $w$ bitem ${\ displaystyle n}$ systemie binarnym. Oznacza to, że jeśli $ma -ty$$n$ równy -th bit equal to 0, the corresponding set does not contain any elements. Each of the subset has the same property as the original static data structure. Operations performed on the new dynamic data structure may involve traversing $\log _{2}\left(n\right)$ sets formed by decomposition. As a result, this will add $O(\log \left(n\right))$ factor as opposed to the static data structure operations but will allow insert/delete operation to be added.

Kurt Mehlhorn udowodnił kilka równań na złożoność czasową operacji na zdynamizowanych zgodnie z tą ideą strukturach danych. Niektóre z tych równości są wymienione.

Jeśli

• ${\ Displaystyle P_ {S} \ lewo (n \ prawo)}$ to czas na zbudowanie statycznej struktury danych
• ${\ Displaystyle Q_ {S} \ lewo (n \ prawo)}$ to czas na zapytanie statycznej struktury danych
• ${\ Displaystyle Q_ {D} \ lewo (n \ prawo)}$ to czas na zapytanie dynamicznej struktury danych utworzonej przez rozkład
• ${\ displaystyle {\ overline {I}}}$ to zamortyzowany czas wstawiania

Następnie

• ${\ Displaystyle Q_ {D} \ lewo (n \ prawo) = O \ lewo (Q_ {S} \ lewo (n \ prawo) \cdot \log \left(n\right)\right)}$
• ${\ Displaystyle {\ overline {I}} = O \ lewo (\ lewo (P_ {S} \ lewo (n \ prawo) / n \ prawo) \ cdot \ log \ lewo (n \ prawo) \ prawo).}$

Q ${\ Displaystyle Q_ {S} \ lewo (n \ prawej)}$ jest co najmniej wielomianem , to $Displaystyle Q_ {D} \ lewo (n\right)=O\left(Q_{S}\left(n\right)\right)}$ .

Dalsza lektura

• Kurt Mehlhorn, Struktury danych i algorytmy 3, . Seria EATCS, tom. 3, Springer, 1984.