ダイナミゼーション

コンピュータ サイエンスでは、ダイナミゼーションとは、静的データ構造を動的データ構造に変換するプロセスです。静的データ構造は、非常に優れた機能と高速なクエリを提供しますが、急速に拡大/縮小できないため、その有用性は限られており、入力データが変化する動的な問題の解決には適用できません。ダイナミゼーション技術は、動的なデータ構造を作成するための統一された方法を提供します。

集合内で述語マッチを検索する問題を と定義します。集合がサブセットに分解可能であり、となる結果の統合操作が存在する場合、問題は分解可能です。 ${\displaystyle P}$${\displaystyle M}$${\displaystyle S}$${\displaystyle P(M,S)}$${\displaystyle P}$${\displaystyle S}$${\displaystyle S_{i}}$${\displaystyle +}$${\displaystyle P(M,S)=P(M,S_{0})+P(M,S_{1})+\dots +P(M,S_{n})}$

分解とは、コンピュータ サイエンスで静的データ構造をサイズの異なる小さな単位に分割するために使用される用語です。基本原理は、任意の 10 進数を他の任意の基数の表現に変換できるという考え方です。このトピックの詳細については、「分解 (コンピュータ サイエンス)」を参照してください。簡単にするために、この記事では 2 進数システムを使用しますが、他の任意の基数 (およびフィボナッチ数などの他の可能性) も使用できます。

バイナリシステムを使用する場合、要素のセットはサイズのサブセットに分割され、 ${\displaystyle n}$

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

要素。ここで、 はバイナリの- 番目のビットです 。つまり、の - 番目のビットが0 の場合、対応するセットには要素が含まれません。各サブセットは、元の静的データ構造と同じプロパティを持ちます。新しい動的データ構造で実行される操作には、分解によって形成されたセットのトラバースが含まれる場合があります。その結果、 静的データ構造の操作とは対照的に、係数が追加されますが、挿入/削除操作を追加できるようになります。 ${\displaystyle n_{i}}$${\displaystyle i}$${\displaystyle n}$${\displaystyle n}$${\displaystyle i}$${\displaystyle \log _{2}\left(n\right)}$${\displaystyle O(\log \left(n\right))}$

Kurt Mehlhorn は、このアイデアに従って動的化されたデータ構造に対する操作の時間計算量に関するいくつかの方程式を証明しました。これらの等式のいくつかを次に示します。

もし

• ${\displaystyle P_{S}\left(n\right)}$静的データ構造を構築する時が来た
• ${\displaystyle Q_{S}\left(n\right)}$静的データ構造を照会する時間です
• ${\displaystyle Q_{D}\left(n\right)}$分解によって形成された動的データ構造を照会する時間です
• ${\displaystyle {\overline {I}}}$償却挿入時間

それから

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

が多項式以上の場合には、 となります。 ${\displaystyle Q_{S}\left(n\right)}$${\displaystyle Q_{D}\left(n\right)=O\left(Q_{S}\left(n\right)\right)}$

• Kurt Mehlhorn、「データ構造とアルゴリズム 3」、EATCS シリーズ、第 3 巻、Springer、1984 年。