Dynamisering

Inom datavetenskap är dynamisering processen att omvandla en statisk datastruktur till en dynamisk . Även om statiska datastrukturer kan ge mycket bra funktionalitet och snabba frågor, är deras användbarhet begränsad på grund av deras oförmåga att växa/krympas snabbt, vilket gör dem otillämpliga för lösning av dynamiska problem , där indata ändras. Dynamiseringstekniker ger enhetliga sätt att skapa dynamiska datastrukturer.

Nedbrytbara sökproblem

Vi definierar problemet $P$ för att söka efter predikatet $M$ -matchningen i uppsättningen $S$ som $P(M,S)$ . Problem $P$ är nedbrytbart om mängden $S$ kan dekomponeras i delmängder $S_{i}$ och det finns en operation $+$ för resultatförening så att $P(M,S)=P(M,S_{0})+ P(M,S_{1})+\dots +P(M,S_{n})$ .

Sönderfall

Nedbrytning är en term som används inom datavetenskap för att bryta statiska datastrukturer i mindre enheter av olika storlek. Grundprincipen är idén att vilket decimaltal som helst kan översättas till en representation i vilken annan bas som helst. För mer information om ämnet se Nedbrytning (datavetenskap) . För enkelhetens skull kommer binära system att användas i den här artikeln men vilken annan bas som helst (liksom andra möjligheter som Fibonacci-tal ) kan också användas.

Om du använder det binära systemet, bryts en uppsättning av ${\displaystyle n} element upp i delmängder av storlekar med$

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

element där $n_{i}$ är den $i$ -te biten av $n$ i binär. Detta betyder att om $n$ har $i$ -th bit lika med 0, innehåller motsvarande uppsättning inga element. Var och en av delmängderna har samma egenskap som den ursprungliga statiska datastrukturen. Operationer som utförs på den nya dynamiska datastrukturen kan innebära att man korsar $\log _{2}\left(n\right)$ uppsättningar som bildats genom nedbrytning. Som ett resultat kommer detta att lägga till $O(\log \left(n\right))$ faktor i motsats till de statiska datastrukturoperationerna men tillåter att infoga/radera operationen kan läggas till .

Kurt Mehlhorn bevisade flera ekvationer för tidskomplexitet för operationer på datastrukturer som dynamiserats enligt denna idé. Några av dessa jämställdheter är listade.

Om

• $P_{S}\left(n\right)$ är tiden för att bygga den statiska datastrukturen
• $Q_{S}\left(n\right)$ är tiden för att fråga den statiska datastrukturen
• $Q_{D}\left(n\right)$ är tiden för att fråga den dynamiska datastrukturen som bildas av nedbrytning
• ${\overline {I}}$ är den amorterade insättningstiden

sedan

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

Om $Q_{S}\left(n\right)$ är åtminstone polynom , då $Q_{D}\left (n\right)=O\left(Q_{S}\left(n\right)\right)$ .

Vidare läsning

• Kurt Mehlhorn, Datastrukturer och algoritmer 3, . An EATCS Series, vol. 3, Springer, 1984.