これは本の段落です: アルゴリズム入門、第 3 版。p.336
「これらの2 つのアプローチは、同じ漸近的な実行時間でアルゴリズムを生成します。トップダウン アプローチが実際にすべての可能な部分問題を調べるために再帰しないという異常な状況を想定してください。ボトムアップ アプローチは、オーバーヘッドが少ないため、多くの場合、はるかに優れた定数係数を持ちます。手続き呼び出しのために。」
コンテキスト : 2 つのアプローチは、最初のトップダウン + メモ化 (DP) と 2 つ目のボトムアップの方法です。
もう1つ質問があります。関数呼び出しの「オーバーヘッド」は、すべての関数呼び出しに時間がかかることを意味しますか? すべてのサブ問題を解決したとしても、「オーバーヘッド」のためにトップダウンの方が時間がかかりますか?
動的計画法のボトムアップアプローチとは、最初にすべての小さな問題を解決し、次にそれらを使用して次に小さな問題への答えを見つけるということです。したがって、たとえば、長さ n の問題の解が長さ n-1 の問題に対する答えだけに依存する場合、長さ 0 のすべての解を入れることから始めて、長さ 1 までの解を繰り返し埋めます。 、2、3 など、毎回、前のレベルですでに計算した答えを使用します。サブ問題を 2 回解く必要がないという点で効率的です。
メモ化アプローチを使用したトップダウンは、逆の見方をします。長さ 10 の問題の解が必要な場合は、再帰的に行います。長さ 9 の 3 つの問題に (たとえば) 依存していることに気付くので、それらを再帰的に解き、長さ 10 の答えを知っています。サブ問題への回答では、最初にそれを既に解決しているかどうかを確認し、解決済みの場合はキャッシュされた回答を返します。
forボトムアップ アプローチは、再帰的にではなく反復的に (ループを使用して) 記述できるという点で優れています。つまり、大きな問題でスタック スペースが不足することはなく、ループも高速です。その欠点は、すべてのサブ問題を解決することであり、答えが必要な大きな問題を解決するためにすべてを解決する必要がない場合があります。
再帰オーバーヘッドのために、とにかくすべてのサブ問題を解決する必要がある場合、トップダウン アプローチは遅くなります。しかし、解決しようとしている問題がサブ問題の小さなサブセットのみを解決する必要がある場合は、必要なものだけを解決するため、より高速です。
これは、熱心な評価(ボトムアップ) と遅延評価(トップダウン)の違いと本質的に同じです。