JS動的プログラミングの使い方を詳しく解説

今回は、JS動的プログラミングの使用について詳しく説明します。JS動的プログラミングを使用する際の注意点は何ですか?実際の事例を見てみましょう。

実際、私たちのフロントエンド開発では、ほとんどの場合、if ステートメント、for ステートメント、switch ステートメントなどを解決できる高度なアルゴリズムはあまり使用されていません。もう少し複雑な場合は、再帰を使用して解決することを考えるかもしれません。

ただし、再帰は書くのは簡単ですが、実際には実行があまり効率的ではないことに注意してください。

動的計画法アルゴリズムをもう一度見てみましょう:

動的プログラミング ソリューションは、根本的な部分から開始してすべての小さな問題を解決し、次にそれらを組み合わせて全体的なソリューションを作成し、大きな問題全体を解決します。

例 (フィボナッチ数列の計算)

フィボナッチ数列とは、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946の一連の数字を指します。 、17711、28657、46368...

このシーケンスは項目 3 から始まり、各項目は前の 2 つの項目の合計に等しくなります。

このシーケンスでは、再帰的関数を使用して、n 番目の項目値

// 斐波那契数列
function recurFib(n) {
    if(n ");
      return recurFib(n-1)+recurFib(n-2)
    }
}

を計算できます。 確かに、上記のコメント付きコードは、n = のときに関数を実行する必要がある回数を出力するために使用されていますが、目の肥えた人であれば、n が増加するにつれて実行回数が増加することが一目でわかります。 . とても恐ろしい成長です。

n=5のとき、再帰木は非常に大きくなりました... n=10、さらにはn=100のときも...

再帰関数の実行効率の違いを理解して、動的プログラミングがどのように行われるかを見てみましょう

function dynFib(n) {
  let val = [];
  for(let i = 0; i <p style="text-align: left;">
中間結果は配列 val に保存されます。計算対象のフィボナッチ数が 1 または 2 の場合、if ステートメントは 1 を返します。 それ以外の場合、値 1 と 2 は val 配列の位置 1 と 2 に格納されます。 </p><p style="text-align: left;">
ループは 3 から入力パラメーターまで移動し、配列の各要素を最初の 2 つの要素の合計に割り当てます。ループが終了すると、配列の最後の要素の値が最終的に計算されたフィボナッチ値になります。 <a href="http://www.php.cn/code/6029.html" target="_blank">関数の戻り値</a>として使用されます。 </p><p style="text-align: left;">
次に、2 つの実行時間を比較する簡単なテスト関数を作成できます。 </p>りー<p style="text-align: left;">
印刷機能の実行</p><pre class="brush:php;toolbar:false">// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

結果は以下の通りです:

最後に、反復アプローチを使用する場合、配列を使用せずにフィボナッチ数列を計算できることに気づいたかもしれません。

配列が必要な理由は、動的プログラミング アルゴリズムでは通常、中間結果を保存する必要があるためです。

以下は、フィボナッチ関数の反復バージョンです

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

もちろん、この反復バージョンの効率は配列バージョンの効率と同じです。

この記事の事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨読書:

Angular4の入出力の使用方法

Vue2.0でユーザー権限を操作する方法

以上がJS動的プログラミングの使い方を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。