コンピュータサイエンスにおいて、動的問題とは、入力データが変化するという観点から定式化された問題のことである。最も一般的な形式では、このカテゴリの問題は通常次のように定式化される。
- オブジェクトから構成される構造が与えられたとき、その構造に関する特定のクエリに効率的に応答するアルゴリズムとデータ構造を見つけるとともに、構造内のオブジェクトの挿入、削除、変更などの更新操作を効率的にサポートする。
このクラスの問題は、以下の複雑さの尺度で表されます。
- スペース–データ構造を格納するために必要なメモリ容量。
- 初期化時間–データ構造の初期構築に必要な時間。
- 挿入時間–入力要素が1つ追加された際に、データ構造の更新に必要な時間。
- 削除時間–入力要素が削除された際にデータ構造を更新するために必要な時間。
- クエリ時間–クエリに回答するのに必要な時間。
- 当該問題に特有のその他の操作
動的問題に対する一連の計算処理全体を動的アルゴリズムと呼ぶ。
固定入力データに基づいて記述される多くのアルゴリズム問題（この文脈では静的問題と呼ばれ、静的アルゴリズムによって解決される）には、意味のある動的バージョンが存在する。
特別なケース
増分アルゴリズム、またはオンラインアルゴリズムとは、要素の追加のみが許容され、場合によっては空のデータや自明な入力データから開始できるアルゴリズムのことである。
デクリメンタルアルゴリズムとは、完全なデータ構造の初期化から始まり、要素の削除のみが許可されるアルゴリズムのことである。
追加と削除の両方が許可されている場合、そのアルゴリズムは完全動的と呼ばれることがあります。
例
最大要素
- 静的問題
- N個の数値の集合の中から、最大の数値を求めよ。
この問題はO( N )の時間で解決できる可能性がある。
- 動的問題
- 初期値としてN個の数値が与えられ、挿入と削除が許可される場合でも、最大値を動的に維持する。
これは、挿入と削除を許容する優先度キューの維持問題です。これは、たとえば バイナリヒープを使用して解決できます。
アップデートの時間です
クエリの時間、
セットアップ時間（つまり、データの初期処理時間）。なお、Nの値は構造物の寿命期間中に変化する可能性があることに注意してください。
グラフ
与えられたグラフに対して、エッジの挿入や削除が可能な場合でも、接続性、最大次数、最短経路などのパラメータを維持する。[ 1 ]
例：
- 重み付き無向グラフの最小全域森林を、エッジの削除と挿入を考慮して維持するアルゴリズムが存在する。
更新にかかる時間。[ 2 ] - 重み付き無向グラフの最小全域森林を、エッジの削除と挿入を考慮して維持するアルゴリズムが存在する。
更新ごとの償却時間。 [ 3 ]
参考文献
- ↑ D. Eppstein、 Z. Galil、 GF Italiano。「動的グラフアルゴリズム」。CRC Handbook of Algorithms and Theory of Computation、第22章。CRC Press、1997年。
- ↑ Eppstein, David; Italiano, Giuseppe; Nissenzweig, Amnon (1997). "Sparsification—a technique for speeding up dynamic graph algorithms". Journal of the ACM . 44 (5): 669–696 . doi : 10.1145/265910.265914 .
- ↑ Henzinger, Monika; King, Valerie (2001). "動的グラフにおける最小全域フォレストの維持" . SIAM Journal on Computing . 31 (2): 364–374 . doi : 10.1137/S0097539797327209 .
