JavaScript の高度なアルゴリズムの動的プログラミング例の分析-jsチュートリアル-php.cn

JavaScript の高度なアルゴリズムの動的プログラミング例の分析

小云云

リリース： 2017-12-07 16:01:11

オリジナル

2016 人が閲覧しました

実際、私たちのフロントエンド開発では、ほとんどの場合、if ステートメント、for ステートメント、switch ステートメントなどを解決できる高度なアルゴリズムはあまり使用されていません。もう少し複雑な場合は、再帰を使用して解決することを考えるかもしれません。この記事では、主に高度な JavaScript プログラミングアルゴリズムの動的プログラミングを紹介し、JavaScript 動的プログラミングアルゴリズムの原理、実装テクニック、および関連する使用上の注意事項をサンプルの形式で分析します。

ただし、再帰は記述が簡単ですが、実際の実行効率は高くないことに注意してください。

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

動的計画ソリューションは、問題を解決するために下から開始し、すべての小さな問題を解決してから、それらを全体的な解決策にマージして大きな問題全体を解決します。

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

フィボナッチ数列とは、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 < 2){
      return n ;
    }else {
//          document.write("第"+(n-1)+"次计算 n-1="+(n-1)+recurFib(n-1)+&#39;   &#39;);
//          document.write("n-2="+(n-2)+recurFib(n-2)+"<br>");
      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 <= n; ++i){
    val[i]=0;
  }
  if(n ===1 || n === 2){
    return 1;
  }
  else {
    val[1] =1;
    val[2] = 2;
    for(let i = 3; i <= n; ++i){
      val[i] = val [i-1] +val[i-2] ;
    }
  }
  return val[n-1]
}

ログイン後にコピー

中間結果は配列 val に保存されます。計算するフィボナッチ数が 1 または 2 の場合、if ステートメントは 1 を返します。それ以外の場合、値 1 と 2 は val 配列の位置 1 と 2 に格納されます。

ループは 3 から入力パラメーターまで移動し、配列の各要素を最初の 2 つの要素の合計に割り当て、ループは終了し、配列の最後の要素の値が、最終的に計算されたフィボナッチ数値になります。関数の戻り値としても使用されます。

次に、2 つの実行時間を比較する簡単なテスト関数を作成できます。

// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write(&#39;<br>&#39;+&#39;当n=&#39;+n+&#39;的时候 &#39;+res+&#39;<br>&#39;);
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

ログイン後にコピー

Print 関数の実行

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

ログイン後にコピー

結果は次のとおりです:

最後に、iter を使用してフィボナッチ数列を計算すると、次のことがわかりました。アクティブなスキーム、それ配列を使用する必要はありません。

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

フィボナッチ関数の反復版の意味は以下の通りです

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i < n; ++i) {
    result = last + nextLast;
    nextLast = last;
    last = result;
  }
  return result;
}

ログイン後にコピー

もちろん、この反復版の効率は配列版と同じです。