ダイナミゼーション

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

問題を定義する${\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}$要素は、サイズごとにサブセットに分割されます。

$2i*ni$

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

クルト・メルホルンは、この考え方に基づいて動的化されたデータ構造に対する操作の時間計算量に関するいくつかの等式を証明した。これらの等式の一部を以下に示す。

もし

• ${\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 年。