Dynamic programming example analysis of JavaScript advanced algorithms

In fact, in our front-end development, there are not many advanced algorithms used. In most cases, if statements, for statements, switch statements, etc. can be solved. If it's a little more complicated, you might think of using recursion to solve it. This article mainly introduces the dynamic programming of advanced JavaScript programming algorithms, and analyzes the principles, implementation techniques and related usage precautions of the JavaScript dynamic programming algorithm in the form of examples. Friends in need can refer to it.

But it should be noted that recursion is simple to write, but its actual execution efficiency is not high.

Let’s take a look at the dynamic programming algorithm:

Dynamic programming solution starts from the bottom to solve the problem, solves all the small problems, and then merges them into an overall solution to solve the entire problem. Big problem.

Example (Calculating Fibonacci Sequence)

The Fibonacci Sequence refers to a sequence of 1, 1, 2, 3, 5, 8, 13, 21, 34 , 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368...

This sequence starts from the 3rd item Initially, each term is equal to the sum of the previous two terms.

For this sequence, you can use a recursive function to calculate the nth value

// 斐波那契数列
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)
    }
}

It is indeed a very The concise code, with the commented code above, is used to print out how many times the function needs to be executed when n =. However, a discerning person can see at a glance that the number of executions will increase horribly as n increases. .

When n=5, the recursion tree has grown very big... It can be predicted that when n=10, or even n=100...

Understanding the difference in execution efficiency of recursive functions, let’s look at how dynamic programming is done

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]
}

Through the array val The intermediate result is saved in . If the Fibonacci number to be calculated is 1 or 2, then the if statement will return 1. Otherwise, the values ​​1 and 2 will be stored at positions 1 and 2 in the val array.

The loop will traverse from 3 to the input parameters, and assign each element of the array to the sum of the first two elements. The loop ends, and the last element value of the array is the final calculated value. Fibonacci value, this value will also be used as the return value of the function.

Next, you can write a simple test function to compare the running time of the two.

// 定义一个测试函数，将待测函数作为参数传入
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 function execution

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

The results are as follows:

Finally, you may have realized that when using an iterative scheme to calculate the Fibonacci sequence, you do not need to use an array.

The reason why arrays are needed is because dynamic programming algorithms usually need to save intermediate results.

The following is the iterative version of the Fibonacci function definition

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;
}

Of course, this iterative version is the same as the array The efficiency of the version is also the same.

Related recommendations:

php algorithm learning of dynamic programming

php algorithm learning of Dynamic programming (2)

Detailed explanation of the change problem of dynamic programming

The above is the detailed content of Dynamic programming example analysis of JavaScript advanced algorithms. For more information, please follow other related articles on the PHP Chinese website!