ダイナミゼーション

コンピュータサイエンスにおいて、ダイナミゼーションとは、静的なデータ構造を動的なデータ構造に変換するプロセスを指します。^{[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}$

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

要素 は、2進数で の- 番目のビットです 。つまり、の- 番目のビットが 0 の場合、対応するセットには要素が含まれません。各サブセットは、元の静的データ構造と同じプロパティを持ちます。新しい動的データ構造に対して実行される操作には、分解によって形成されたセットの走査が含まれる場合があります。その結果、 静的データ構造の操作とは対照的に、係数が追加されますが、挿入/削除操作を追加できます。 ${\displaystyle n_{i}}$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\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)}$

参考文献

1. Mathieu, Claire; Rajaraman, Rajmohan; Young, Neal E.; Yousefi, Arman (2024-10-11). "Competitive Data-Structure Dynamization". ACM Trans. Algorithms . 20 (4): 37:1–37:28. arXiv : 2011.02615 . doi :10.1145/3672614. ISSN  1549-6325.ダイナミゼーションは、静的なコンテナデータ構造を、任意の挿入とクエリを混在させた動的なデータ構造に変換するための汎用的な手法です。

さらに読む

• Kurt Mehlhorn, Data structures and algorithms 3, EATCSシリーズ第3巻、Springer、1984年。