Dynamization

Dynamization

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 fast, thus making them inapplicable for the solution of dynamic problems, where the amount of the input data changes. Dynamization techniques provide uniform ways of creating dynamic data structures.

Decomposable search problems

We define problem P of searching for the predicate M match in the set S as P(M,S). Problem P is decomposable if the set S can be decomposed into subsets Si and there exist an operation + of result unification such that 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 elements is broken down into subsets of sizes with

2i * ni

elements where ni is the i-th bit of n in binary. This means that if n has 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}\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 proved several equations for time complexity of operations on data structures dynamized according to this idea. Some of these equalities are listed.

If

P_S\left(n\right)\,\! = time to build the static data structure
Q_S\left(n\right)\,\! = time to query the static data structure
Q_D\left(n\right)\,\! = time to query the dynamic data structure formed by decomposition
\overline{I} = amortized insertion time

Then

 Q_D\left(n\right) = O(Q_S\left(n\right)\log\left(n\right))\,\!
 \overline{I}=O(\left(P_S\left(n\right)/n\right)\log\left(n\right))

If Q_S\left(n\right) is at least polynomial, then Q_D\left(n\right)=O\left(Q_S\left(n\right)\right).

Further reading

Kurt Mehlhorn, Data structures and algorithms 3, . An EATCS Series, vol. 3, Springer, 1984.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Dynamization — Dy na*mi*za tion, [Gr. ? power. See {Dynamic}.] (Homeop.) The act of setting free the dynamic powers of a medicine, as by shaking the bottle containing it. [1913 Webster] …   The Collaborative International Dictionary of English

  • dynamization — noun A hypothetical increase of medicinal effectiveness by dilution and trituration …   Wiktionary

  • dynamization — dy·na·mi·za·tion …   English syllables

  • dynamization — ˌdīnəmə̇ˈzāshən, ˌmīˈz noun ( s) : the act or an instance of dynamizing …   Useful english dictionary

  • dynamize — dynamization, n. /duy neuh muyz /, v.t., dynamized, dynamizing. to make more active, productive, or the like; energize: an attempt to dynamize the local economy. Also, esp. Brit., dynamise. [1880 85; DYNAM(IC) + IZE] * * * …   Universalium

  • The Organon of the Healing Art — (Organon der rationellen Heilkunde) by Samuel Hahnemann, 1810, laid the foundations of all theory and method of classical homeopathy [ [http://www.hompath.net/homeopathy/organon of the healing art.php Organon of the Healing Art] ] . The work was… …   Wikipedia

  • Homeopathy — Homeopathy: coined in German from Greek hómoios ὅμοιος like + páthos πάθος suffering Oxford English Dictionary …   Wikipedia

  • dynamisation — [ dinamizasjɔ̃ ] n. f. • 1955; angl. dynamization → dynamiser 1 ♦ Pharm. Action d accroître l efficacité d un remède par des procédés de préparation spécifiquement homéopathiques : dilution, trituration. 2 ♦ (v. 1960) Action de dynamiser (2o).… …   Encyclopédie Universelle

  • Data structure — In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”