집 > 기사 > 웹 프론트엔드 > JavaScript 고급 알고리즘의 동적 프로그래밍 예제 분석

JavaScript 고급 알고리즘의 동적 프로그래밍 예제 분석

小云云원래의: 2017-12-07 16:01:112003검색

실제로 우리 프론트엔드 개발에서는 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번째 항목부터 시작되며, 각 항목은 이전 두 항목의 합과 같습니다.

이 시퀀스에서는 재귀 함수를 사용하여 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부터 입력 매개변수까지 순회하고, 배열의 각 요소를 처음 두 요소의 합에 할당하고, 루프가 종료되며, 배열의 마지막 요소 값은 최종 계산된 피보나치 값입니다. 함수의 반환 값으로도 사용됩니다.

다음으로 두 가지의 실행 시간을 비교하는 간단한 테스트 함수를 작성할 수 있습니다.

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

결과는 다음과 같습니다.

마지막으로, 반복을 사용하여 피보나치 수열을 계산할 때 계획, 그것은 배열을 사용할 필요는 없습니다.

배열이 필요한 이유는 동적 프로그래밍 알고리즘이 일반적으로 중간 결과를 저장해야 하기 때문입니다.

다음은 피보나치 함수의 반복 버전의 의미입니다

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

물론, 이 반복 버전의 효율성은 배열 버전과 동일합니다.

JavaScript 고급 알고리즘의 동적 프로그래밍 예제 분석

관련 기사