Misplaced Pages

Dynamization

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Process of transforming a static data structure into a dynamic one
This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Dynamization" – news · newspapers · books · scholar · JSTOR (February 2023) (Learn how and when to remove this message)

In computer science, dynamization is the process of transforming a static data structure into a dynamic one. Although static data structures may provide very good functionality and fast queries, their utility is limited because of their inability to grow/shrink quickly, thus making them inapplicable for the solution of dynamic problems, where the input data changes. Dynamization techniques provide uniform ways of creating dynamic data structures.

Decomposable search problems

We define problem P {\displaystyle P} of searching for the predicate M {\displaystyle M} match in the set S {\displaystyle S} as P ( M , S ) {\displaystyle P(M,S)} . Problem P {\displaystyle P} is decomposable if the set S {\displaystyle S} can be decomposed into subsets S i {\displaystyle S_{i}} and there exists an operation + {\displaystyle +} of result unification such that P ( M , S ) = P ( M , S 0 ) + P ( M , S 1 ) + ⋯ + P ( M , S n ) {\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})} .

Decomposition

Decomposition is a term used in computer science to break static data structures into smaller units of unequal size. The basic principle is the idea that any decimal number can be translated into a representation in any other base. For more details about the topic see Decomposition (computer science). For simplicity, binary system will be used in this article but any other base (as well as other possibilities such as Fibonacci numbers) can also be utilized.

If using the binary system, a set of n {\displaystyle n} elements is broken down into subsets of sizes with

2 i ∗ n i {\displaystyle 2^{i}*n_{i}}

elements where n i {\displaystyle n_{i}} is the i {\displaystyle i} -th bit of n {\displaystyle n} in binary. This means that if n {\displaystyle n} has i {\displaystyle i} -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 ⁡ ( n ) {\displaystyle \log _{2}\left(n\right)} sets formed by decomposition. As a result, this will add O ( log ⁡ ( n ) ) {\displaystyle 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 proved several equations for time complexity of operations on the data structures dynamized according to this idea. Some of these equalities are listed.

If

  • P S ( n ) {\displaystyle P_{S}\left(n\right)} is the time to build the static data structure
  • Q S ( n ) {\displaystyle Q_{S}\left(n\right)} is the time to query the static data structure
  • Q D ( n ) {\displaystyle Q_{D}\left(n\right)} is the time to query the dynamic data structure formed by decomposition
  • I ¯ {\displaystyle {\overline {I}}} is the amortized insertion time

then

  • Q D ( n ) = O ( Q S ( n ) ⋅ log ⁡ ( n ) ) {\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\cdot \log \left(n\right)\right)}
  • I ¯ = O ( ( P S ( n ) / n ) ⋅ log ⁡ ( n ) ) . {\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n\right)/n\right)\cdot \log \left(n\right)\right).}

If Q S ( n ) {\displaystyle Q_{S}\left(n\right)} is at least polynomial, then Q D ( n ) = O ( Q S ( n ) ) {\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)} .

Further reading

Category: