집 >웹 프론트엔드 >JS 튜토리얼 >JS 동적 프로그래밍 사용에 대한 자세한 설명

JS 동적 프로그래밍 사용에 대한 자세한 설명

php中世界最好的语言원래의: 2018-04-14 13:56:421816검색

이번에는 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부터 시작하며 각 항목은 이전 두 항목의 합계와 같습니다.

이 시퀀스의 경우 재귀 함수를 사용하여 n번째 항목 값

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

을 계산할 수 있습니다. 실제로는 매우 간결한 코드입니다. 위의 주석 처리된 코드는 n =일 때 함수를 몇 번 실행해야 하는지 출력하는 데 사용됩니다. 그러나 안목 있는 사람은 n이 증가함에 따라 실행 횟수가 증가한다는 것을 한눈에 알 수 있습니다. . 매우 무서운 성장.

JS 동적 프로그래밍 사용에 대한 자세한 설명

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에서 입력 매개변수까지 이동하고 배열의 각 요소를 처음 두 요소의 합에 할당합니다. 루프가 끝나면 배열의 마지막 요소 값이 최종 계산된 피보나치 값이 됩니다. <a href="http://www.php.cn/code/6029.html" target="_blank"> 함수의 반환 값 </a>으로 사용됩니다. </p><p style="text-align: left;">
다음으로 두 함수의 실행 시간을 비교하는 간단한 테스트 함수를 작성할 수 있습니다. </p>rreee<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";//返回函数执行需要时间
}

결과는 다음과 같습니다:

JS 동적 프로그래밍 사용에 대한 자세한 설명

마지막으로, 반복적 접근 방식을 사용할 때 배열을 사용하지 않고 피보나치 수열을 계산하는 것이 가능하다는 것을 깨달았을 것입니다.

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

다음은

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

를 의미하는 피보나치 함수의 반복 버전입니다. 물론 이번 반복 버전의 효율성은 어레이 버전과 동일하다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!