フィボナッチ：トップダウンとボトムアップの動的計画法

1. 序章

このチュートリアルでは、フィボナッチ数列の数値を計算するための3つの一般的なアプローチ、再帰的アプローチ、トップダウン動的計画法アプローチ、およびボトムアップ動的アプローチについて説明します。プログラミングアプローチ。

フィボナッチ数列は整数のシーケンスであり、シリーズの次の整数は前の2つの合計です。

これは、次の再帰式によって定義されます。

フィボナッチ数列の項を計算する方法はたくさんあります。以下では、3つの一般的なアプローチを見ていきます。

再帰的アプローチで計算するには、最初にとの解を見つけようとします。しかし、を見つけるには、を見つける必要があります。これは、基本ケースに到達するまで続きます：および。

下の画像では、以下を取得するために解決する必要のあるサブ問題のツリーを見ることができます。

このアプローチの欠点の1つは、ソリューションを取得するために同じフィボナッチ数を複数回計算する必要があることです。

この冗長な作業を取り除くことができるかどうか見てみましょう。

使用する最初の動的計画法アプローチは、トップダウンアプローチです。ここでの考え方は再帰的アプローチに似ていますが、違いは発生したサブ問題の解決策を保存することです。

このようにして、同じサブ問題に複数回遭遇した場合、再計算する代わりに、保存したソリューションを使用できます。これにより、各サブ問題を1回だけ計算できます。

この動的計画法はメモ化と呼ばれます。メモ化を使用すると、サブ問題のツリーがどのように縮小するかを確認できます。

ボトムアップ動的計画法のアプローチでは、サブ問題を解決する順序を再編成します。

を計算し、次に、、というように計算します。

これにより、各問題の解を1回だけ計算でき、一度に2つの中間結果を保存するだけで済みます。

たとえば、私たちが見つけようとしているとき、私たちは解決策を持っていて利用可能である必要があるだけです。同様に、の場合、との解があれば十分です。

これにより、コードで使用するメモリスペースを減らすことができます。

再帰的なソリューションでは、再帰的な式を擬似コードに変換するだけです。

トップダウンアプローチでは、サブ問題の解決策を保存するためにアレイを設定する必要があります。ここでは、ヘルパー関数で作成してから、メイン関数を呼び出します。

それでは、メインのトップダウン機能を見てみましょう。再帰的アプローチで行ったように、サブ問題の解を計算する前に、配列に格納されている解を返すことができるかどうかを常に確認します。

ボトムアップアプローチでは、に達するまでフィボナッチ数を順番に計算します。この順序で計算するため、中間結果を格納するためにサイズの配列を保持する必要はありません。

代わりに、変数を使用して、最近計算された2つのフィボナッチ数を保存します。これは、シリーズの次の数値を計算するのに十分です。

再帰的ソリューションの時間計算量は指数関数的です–正確には。これは、同じサブ問題を複数回解決するためです。

トップダウンアプローチでは、各サブ問題を1回だけ解決します。各サブ問題の解決には一定の時間がかかるため、これにより時間計算量がになります。ただし、中間結果を保存するためにサイズの配列を保持する必要があるため、このアルゴリズムのスペースの複雑さもです。

ボトムアップアプローチでは、各サブ問題も1回だけ解決します。したがって、アルゴリズムの時間計算量もです。中間結果を追跡するために2つの変数のみを使用するため、スペースの複雑さは一定です。

これは、再帰的アプローチの時間計算量を動的計画法アプローチの時間計算量に対してプロットしたグラフです。

この記事では、再帰的アプローチと2つの動的計画法アプローチを使用してフィボナッチ数列の数値を計算する方法について説明しました。

また、これらのアルゴリズムの擬似コードを調べ、時間と空間の複雑さについて説明しました。