Dynamisation

En informatique , la dynamisation est le processus de transformation d'une structure de données statique en une structure dynamique. Bien que les structures de données statiques puissent offrir de très bonnes fonctionnalités et des requêtes rapides, leur utilité est limitée en raison de leur incapacité à croître/rétrécir rapidement, ce qui les rend inapplicables à la résolution de problèmes dynamiques , où les données d'entrée changent. Les techniques de dynamisation fournissent des moyens uniformes de créer des structures de données dynamiques.

Problèmes de recherche décomposables

Nous définissons le problème de recherche de la correspondance de prédicat dans l'ensemble comme . Le problème est décomposable si l'ensemble peut être décomposé en sous-ensembles et s'il existe une opération d'unification du résultat telle que . ${\displaystyle P <semantics> <mrow> <mstyle> <mi>P</mi> </mstyle> </mrow> <annotation>{\displaystyle P}</annotation> </semantics> </math><img src=$ ${\displaystyle M <semantics> <mrow> <mstyle> <mi>M</mi> </mstyle> </mrow> <annotation>{\displaystyle M}</annotation> </semantics> </math><img src=$ ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle P(M,S) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <mi>M</mi> <mo>,</mo> <mi>S</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P(M,S)}</annotation> </semantics> </math><img src=$ ${\displaystyle P <semantics> <mrow> <mstyle> <mi>P</mi> </mstyle> </mrow> <annotation>{\displaystyle P}</annotation> </semantics> </math><img src=$ ${\displaystyle S <semantics> <mrow> <mstyle> <mi>S</mi> </mstyle> </mrow> <annotation>{\displaystyle S}</annotation> </semantics> </math><img src=$ ${\displaystyle S_{i <semantics> <mrow> <mstyle> <msub> <mi>S</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle S_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle + <semantics> <mrow> <mstyle> <mo>+</mo> </mstyle> </mrow> <annotation>{\displaystyle +}</annotation> </semantics> </math><img src=$ ${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n}) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <mi>M</mi> <mo>,</mo> <mi>S</mi> <mo>)</mo> <mo>=</mo> <mi>P</mi> <mo>(</mo> <mi>M</mi> <mo>,</mo> <msub> <mi>S</mi> <mrow> <mn>0</mn> </mrow> </msub> <mo>)</mo> <mo>+</mo> <mi>P</mi> <mo>(</mo> <mi>M</mi> <mo>,</mo> <msub> <mi>S</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>)</mo> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <mi>P</mi> <mo>(</mo> <mi>M</mi> <mo>,</mo> <msub> <mi>S</mi> <mrow> <mi>n</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}</annotation> </semantics> </math><img src=$

Décomposition

La décomposition est un terme utilisé en informatique pour décomposer des structures de données statiques en unités plus petites de taille inégale. Le principe de base est l'idée que tout nombre décimal peut être traduit en une représentation dans n'importe quelle autre base. Pour plus de détails sur le sujet, voir Décomposition (informatique) . Pour plus de simplicité, le système binaire sera utilisé dans cet article mais toute autre base (ainsi que d'autres possibilités telles que les nombres de Fibonacci ) peut également être utilisée.

Si l'on utilise le système binaire, un ensemble d' éléments est décomposé en sous-ensembles de tailles avec ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$

{\displaystyle 2^{i}*n_{i <semantics> <mrow> <mstyle> <msup> <mn>2</mn> <mrow> <mi>je</mi> </mrow> </msup> <mo>∗</mo> <msub> <mi>n</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle 2^{i}*n_{i}}</annotation> </semantics> </math></span><img src=

éléments où est le -ième bit de en binaire. Cela signifie que si le -ième bit est égal à 0, l'ensemble correspondant ne contient aucun élément. Chacun des sous-ensembles possède la même propriété que la structure de données statique d'origine. Les opérations effectuées sur la nouvelle structure de données dynamique peuvent impliquer de parcourir des ensembles formés par décomposition. Par conséquent, cela ajoutera un facteur par opposition aux opérations de structure de données statiques, mais permettra d'ajouter une opération d'insertion/suppression. ${\displaystyle n_{i <semantics> <mrow> <mstyle> <msub> <mi>n</mi> <mrow> <mi>je</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle n_{i}}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle i <semantics> <mrow> <mstyle> <mi>je</mi> </mstyle> </mrow> <annotation>{\displaystyle i}</annotation> </semantics> </math><img src=$ ${\displaystyle \log _{2}\left(n ight) <semantics> <mrow> <mstyle> <msub> <mi>enregistrer</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \log _{2}\gauche(n\droite)}</annotation> </semantics> </math><img src=$ ${\displaystyle O(\log \left(n ight)) <semantics> <mrow> <mstyle> <mi>O</mi> <mo>(</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle O(\log \gauche(n\droite))}</annotation> </semantics> </math><img src=$

Kurt Mehlhorn a démontré plusieurs équations de complexité temporelle d'opérations sur les structures de données dynamisées selon cette idée. Certaines de ces égalités sont listées.

${\displaystyle P_{S}\left(n ight) <semantics> <mrow> <mstyle> <msub> <mi>P</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle P_{S}\gauche(n\droite)}</annotation> </semantics> </math><img src=$
${\displaystyle Q_{S}\left(n ight) <semantics> <mrow> <mstyle> <msub> <mi>Q</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q_{S}\gauche(n\droite)}</annotation> </semantics> </math><img src=$
${\displaystyle Q_{D}\left(n ight) <semantics> <mrow> <mstyle> <msub> <mi>Q</mi> <mrow> <mi>D</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q_{D}\gauche(n\droite)}</annotation> </semantics> </math><img src=$
${\displaystyle {\overline {I <semantics> <mrow> <mstyle> <mrow> <mover> <mi>je</mi> <mo>¯</mo> </mover> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\overline {je}}}</annotation> </semantics> </math><img src=$

alors

${\displaystyle Q_{D}\left(n ight)=O\left(Q_{S}\left(n ight)\cdot \log \left(n ight) ight) <semantics> <mrow> <mstyle> <msub> <mi>Q</mi> <mrow> <mi>D</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>=</mo> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <msub> <mi>Q</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>⋅</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q_{D}\gauche(n\droite)=O\gauche(Q_{S}\gauche(n\droite)\cdot \log \gauche(n\droite)\droite)}</annotation> </semantics> </math><img src=$
${\displaystyle {\overline {I}}=O\left(\left(P_{S}\left(n ight)/n ight)\cdot \log \left(n ight) ight). <semantics> <mrow> <mstyle> <mrow> <mover> <mi>je</mi> <mo>¯</mo> </mover> </mrow> <mo>=</mo> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <mrow> <mo>(</mo> <mrow> <msub> <mi>P</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mrow> <mo>/</mo> </mrow> <mi>n</mi> </mrow> <mo>)</mo> </mrow> <mo>⋅</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mrow> <mo>)</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle {\overline {I}}=O\gauche(\gauche(P_{S}\gauche(n\droite)/n\droite)\cdot \log \gauche(n\droite)\droite).}</annotation> </semantics> </math><img src=$

Si est au moins polynôme , alors . ${\displaystyle Q_{S}\left(n ight) <semantics> <mrow> <mstyle> <msub> <mi>Q</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q_{S}\gauche(n\droite)}</annotation> </semantics> </math><img src=$ ${\displaystyle Q_{D}\left(n ight)=O\left(Q_{S}\left(n ight) ight) <semantics> <mrow> <mstyle> <msub> <mi>Q</mi> <mrow> <mi>D</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>=</mo> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <msub> <mi>Q</mi> <mrow> <mi>S</mi> </mrow> </msub> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q_{D}\gauche(n\droite)=O\gauche(Q_{S}\gauche(n\droite)\droite)}</annotation> </semantics> </math><img src=$

Lectures complémentaires

Kurt Mehlhorn, Structures de données et algorithmes 3, . Une série EATCS, vol. 3, Springer, 1984.