情報科学 › アルゴリズムとデータ構造 › 動的計画法

動的計画法の計算量

定理 3.2（「動的計画法」§3）・ ✓公理まで証明済み

定義 3.1 の意味の部分問題族 $(S, D, g)$ が与えられ、 $N = |S|$ とする。表への読み書きが $1$ ステップででき、各 $s$ について、依存先の値 $V(s_1), \ldots, V(s_{k_s})$ がすでに表にあるという条件のもとで $g_s$ の評価が $c(s)$ ステップでできるとする。このとき、すべての $s \in S$ に対する $V(s)$ を

O\Bigl(N + \sum_{s \in S} c(s)\Bigr)

ステップ、 $O(N)$ の作業領域で計算できる。とくに、ある定数 $c$ が存在してすべての $s \in S$ で $c(s) \le c$ ならば、計算時間は $O(Nc)$ である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 0 件、定義なども含めて 1 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 1 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

部分問題族と依存グラフ定義 3.1・動的計画法

これを使っている定理証明で参照している 5 件

メモ化再帰の計算量✓命題 3.3・動的計画法
フィボナッチ数の線形時間計算✓系 4.2・動的計画法
ナップサック問題の計算量✓系 6.4・動的計画法
BPE の符号化は最短分割とは限らない✓命題 5.1・トークン化
行列の鎖の最小の乗算回数✓定理 5.2・NumPy で書く配列計算

関連するノック 4 問