JavaScript 알고리즘의 반복

사랑과 미움의 - 귀속

귀속

너에게 이야기를 하나 해주면 알겠는데, 무슨 이야기지?
옛날에 산이 있었는데 산에 절이 있었어요. 절에 늙은 스님이 어린 스님께 이야기를 해주고 있었어요. 옛날에 산이 있었는데 산에 절이 있었어요. 절에 늙은 스님이 어린 스님께 이야기를 해주고 있었어요. 옛날에 산이 있었어요.
이것이 바로 전형적인 귀환이다. 나이 등 자신을 고려하지 않는 조건에서 이것은 종지 조건이 없을 것이다.
예를 하나 더 들다.스포일러가 두렵지 않다고 불리는 영화'도몽공간'을 보셨는지 모르겠다.자두 팀들은 임무를 수행할 때마다 수면 모드에 들어간다.만약 꿈속에서 임무를 완수하지 못한다면 다시 꿈속에서 꿈을 꾸고 임무를 계속 수행하라.만약 아직 안 된다면, 다시 한 번 꿈을 꾸어라.마찬가지로 현실로 돌아가야 한다면 가장 깊은 꿈에서 깨어나 첫 번째 꿈으로 돌아가야 한다.
이 과정도 귀환으로 삼을 수 있다.겹겹의 꿈은 건네주고 겹겹이 깨어나면 돌아온다.
귀환은 본질적으로 원래의 문제를 더욱 작은 동일한 문제로 바꾸는 것이다. 대사는 하나의 함수가 끊임없이 자신을 호출하는 것이다.
다음은 Fibonacci 수열을 계산하는 대표적인 예제를 살펴보자.
1,1,2,3,5,8,13,21,34,......x를 가리킨다.
코드는 다음과 같이 표시됩니다.

function Fibonacci (n) {
  if ( n <= 2 ) {return 1};

  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

귀속 3 요소

1. 한 문제의 해답은 몇 개의 더 작은 동일한 문제의 해답으로 분해할 수 있다

예를 들어 위의 수열은 10위수가 몇 fn(10)인지 구하려면 9위수 fn(9)과 8위수 fn(8)이 얼마나 되는지 구하는 것과 유사하게 분해할 수 있다.

2. 분해된 하위 문제는 데이터가 다른 문제만 존재한다.

예를 들어 위의 수열은 매번 분해된 후에 형성된 서브문제 구해 방식이 똑같다. 단지 매번 데이터의 규모가 변했다고 말할 뿐이다.

3. 귀속 중지 조건이 존재합니다

이것은 반드시 존재해야 한다. 문제를 층층이 분해하지만, 무한히 순환할 수는 없다.예를 들어 위의 수열은 n이 2보다 작을 때 멈춘다. 이때 첫 번째 수와 두 번째 수가 얼마나 되는지 이미 알고 있다. 이것이 바로 종지 조건이다.늙은 중이 어린 중에게 이야기를 하는 것처럼 끝이 없어서는 안 된다.

귀속을 실현하다

먼저 간단한 예제를 분석하고 귀속적인 방식으로 수조의 모든 원소의 합을 구한다.
위에서 말한 세 가지 요소에 근거하여 이 문제를 분해해 보자.
구해수 그룹arr의 합은 우리가 첫 번째 수로 분해한 다음에 나머지 수의 합을 더하면 다음과 같이 분해할 수 있다.

 const arr = [1,2,3,4,5,6,7,...,n];
 sum(arr[0]+...+arr[n]) = arr[0] + sum(arr[1]+...+arr[n]);
 sum(arr[1]+...+arr[n]) = arr[1] + sum(arr[2]+...+arr[n]);
                ....
 sum(arr[n]) = arr[n] + sum([]);

그런 다음 다음 다음 공식을 유도할 수 있습니다.

x = 0;
sum(arr, x) = arr[x] + sum(arr,x+1); // x： 

다시 한 번 종지 조건을 고려하면 x가 수조의 길이와 같을 때 멈춰야 하고 이때 0으로 돌아가야 한다.그래서 종합해 보면 우리는 이 문제의 해답을 얻을 수 있다.

{
    function sum(arr) {
        const total = function(arr, l) {
            if(l == arr.length) {
                return 0;
            }
            return arr[l] + total(arr, l + 1);
        }
        return total(arr, 0);
    }
    sum([1,2,3,4,5,6,9,10]);
}

컴포지팅 코드를 쓰는 관건은 원래의 문제를 어떻게 더 작은 동일한 문제로 바꿀 수 있는지 찾아내고 이를 바탕으로 컴포지팅 공식을 쓴 다음에 종지 조건을 추궁하고 마지막으로 컴포지팅 공식과 종지 조건을 최종 코드로 합성하는 것이다.

주의 사항

1. 귀속은 창고가 넘치기 쉽다

함수 호출은 임시 변수를 저장하기 위해 창고를 사용합니다.함수를 호출할 때마다 임시 변수를 창고 프레임으로 봉하여 메모리 창고에 넣고 함수 실행이 끝나면 창고에서 나온다.그러나 귀환은 메모리를 매우 소모한다. 수천 개의 호출 프레임을 동시에 저장해야 하기 때문에 데이터 규모가 비교적 크면'창고 넘침'오류가 발생하기 쉽다(stack overflow).
예를 들어 귀속을 이용하여 곱하기를 구하는 함수:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

그러면 어떻게 이런 실수를 피할 수 있습니까?우리는 코드에 매개 변수를 추가하여 귀속 호출 횟수를 기록할 수 있다.숫자보다 크면 오류 메시지를 수동으로 설정합니다.예를 들어 위의 예:

{
    let count = 0;
    function factorial(n) {
        count ++;
        if (count > 1000) {
            console.error(' ');
            return;
        }
        if (n === 1) return 1;
        return n * factorial(n - 1);
      }
      factorial(2000)
}

물론 이 숫자는 사전에 추산할 수 없기 때문에 최대 깊이가 비교적 낮은 귀속 호출에만 적합하다.

2. 귀속 중의 중복 계산을 경계한다

예를 들어 위에서 언급한 경전의 수열:

function Fibonacci (n) {
  if ( n <= 2 ) {return 1};
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

코드는 매우 간단하지만 대량의 중복 계산을 포함하고 있다.

  f(5)

f(5) = f(4) + f(3)；

  f(4)   f(3)；

  f(4)

f(4) = f(3)+ f(2);

 f(3) f(2);

이를 통해 알 수 있듯이 f(5)와 f(4)에서 모두 f(3)를 계산해야 하지만 이 두 번의 f(3)는 중복 계산을 한다. 이것이 바로 귀속의 가장 큰 문제로 같은 f(n)에 대해서는 복용할 수 없다.
f(n)를 계산하는 데 도대체 몇 번의 귀속 호출이 필요한지 궁금하십니까?
우리는 코드에 계수를 더해서 검증할 수 있다.

{
    let count = 0;
    function Fibonacci (n) {
        count ++;
      if ( n <= 2 ) {return 1};
    
      return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    Fibonacci(n); // n:  
    console.log(count);
}

실험의 결과:

f(5) count = 9

f(10) count = 109

f(25) count = 150049

f(35) count = 18454929

f(40) count = 204668309

f(45) …  ， ， 

당신의 기계에서 코드를 시험해 볼 수 있습니다. 간단한 두 마디 코드의 시간 복잡도는 O의 지수급에 달합니다.
그래서 최적화 알고리즘은 한시도 늦출 수 없다.
중복 계산을 피하기 위해서, 이미 풀린 f (n) 를 저장하는 대상을 사용할 수 있습니다.f(n)로 호출될 때, 먼저 해답을 구했는지 판단합니다.만약 그렇다면 대상에서 직접 값을 추출하여 되돌려주고 계산할 필요가 없다. 그렇지 않으면 다시 되돌려주면 방금 말한 문제를 피할 수 있다.
그래서 최적화된 코드는 다음과 같다.

{
    function Fibonacci() {
        this.obj = {};
        this.count = 0;
    }
    Fibonacci.prototype.getF = function(n) {
        this.count ++;
        if ( n <= 2 ) {return 1};
        if (this.obj.hasOwnProperty(n)) {
            return this.obj[n];
        }
        const ret = this.getF(n - 1) + this.getF(n -2);
        this.obj[n] = ret;
        return ret;
    }
    
    var f = new Fibonacci();
    f.getF(45);
}

캐시를 넣은 후 위의 그림에서 알 수 있듯이 현재의 시간 복잡도는 O(n)에 불과하다.

비귀속 실현

귀속을 이용하여 부족한 점과 우수한 점을 실현하는데 장점은 짧고 세련된 것이다.단점은 공간의 복잡도가 높고 창고가 넘칠 위험이 있으며 중복 계산이 존재하고 과도한 함수 호출은 시간이 많이 소모된다는 것이다.따라서 알고리즘을 선택할 때 실제 상황에 따라 적당한 방식을 선택하여 실현해야 한다.
일반적으로 귀환이 실현할 수 있는 for순환을 모두 실현할 수 있다.예를 들면 윗글의 수조 구화.
이어서 우리는 for 순환으로 피보나치 수열을 고쳤다.
간단합니다. 말은 많이 하지 않고 코드로 바로 보여 줍니다.

{
    function fibonacci(n) {
        if (n === 1 || n === 2) {
            return 1;
        }
        let one = 1;
        let two = 1;
        let temp = null;
        for(let i = 3; i <= n; i++) {
            temp = one + two;     //  
            one = two;
            two = temp;
        }
        return temp;
    }
    console.log(fibonacci(40));
}

이 코드의 시간 복잡도는 한눈에 알아볼 수 있겠지.

총결산

처음에 js를 접했을 때 귀속을 두려워했고 귀속 코드를 거의 쓰지 않았다.그러나 사실 공부를 한 후에 귀환이 여전히 매우 귀엽다는 것을 발견하였다.수학에서 숫자의 법칙을 찾는 것처럼 우리의 사유를 단련시킬 수 있다.
예를 들어 방금 for 순환으로 개작한 피보나치 수열에 대해 다른 해법이 있습니다. 예를 들어 수조로 개작하는 것입니다.
토론에 오신 걸 환영합니다.

기타 최적화 방법

완일봉 선생님이 말씀하신 꼬리표를 참고하여 아래에 연결할 수 있습니다.

참고 문장

ECMAScript 6 시작하기

네가 있어야 완벽해.

스스로 요리를 인정하고 데이터 구조와 알고리즘의 교류군을 만들었습니다. 언어 개발을 제한하지 않고 앞뒤 부분에 있습니다. 여러분의 입주를 환영합니다.

전송문

JavaScript 데이터 구조의 스택

JavaScript 데이터 구조의 대기열

자바스크립트 데이터 구조의 팀 창고 호환

JavaScript 데이터 구조의 체인 테이블 - 소개

JavaScript 데이터 구조의 체인 테이블 - 디자인

자바스크립트 알고리즘의 복잡도 분석

자바스크립트 알고리즘의 가장 좋고 최악의 시간 복잡도 분석

전재 대상:https://juejin.im/post/5c3e9fdbf265da61285a596d