이항 계수 시간 및 공간 복잡도를 계산하는 방법은 무엇입니까? (iterative vs. recursive)

Question

이것은 반복 버전이지만 재귀 함수를 호출합니다. 시간/공간의 복잡성에 영향을 미칠까요?

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

int binomial_coefficient_iterative(unsigned int n, unsigned int k) { 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return (factorial(n)/(factorial(k) * factorial(n - k))); 
    } 
} 

이것은 C (N, K) = C (N-1, K) + C (N-1, K-1)의 식을 사용하여 계산 재귀 버전이다.

int binomial_coefficient_recursive(unsigned int n, unsigned int k){ 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return binomial_coefficient_recursive(n - 1, k) + binomial_coefficient_recursive(n - 1, k - 1); 
    } 
} 

마지막으로, 만약 C를 사용하여 이항 계수 C (N, k)를 산출 할 수있다 (N, K-1)을?

Answer 1

두 솔루션 모두 재귀에 의존합니다. 첫 번째 버전에서는 계승의 재귀 호출을 간단한 반복으로 대체 할 수 있습니다.

그러나 두 번째 해결 방법에서는 중복되는 하위 문제를 다시 계산해야하는 문제가 있습니다.

C(n, k) = C(n-1, k) + C(n-1, k-1) 

당신이 저장 값을 계산하는 기능 대신 계산, 룩업 다시 동일한 parameteres로 호출 할 때 값을 반환 할 때마다 C (N, K)의 값을 캐시하는 메모이 제이션을 사용한다.

첫 번째 문제는 계승 함수를 여러 번 호출하여 피할 수있는 문제입니다. 이 전략은 증분 변경을 계산하는 것입니다. 당신이 계산 예를 들어 factorial(k) 당신이 당신이하고있는 곱셈의 수를 줄일 수

factorial(n) = factorial(k) * K+1 * K+2 ...n 

유도 할 수있다.

문제의 공간 시간 복잡도로 되돌아옵니다.

1 : 그것은

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)   
    where T(n,n) = T(n,0) = O(1) 

것이 차이 방정식을 것입니다 해결 :

는 2 시간 복잡도는 N, K와 북한의 곱셈을하고 호출 여기에 3 계승에 관해서는 O (N)입니다 T (n) = O (2^n) (fibonacci 계열의 복잡성을 찾는 데 사용 된 동일한 인수)

따라서 이후의 접근법은 메모 법을 사용하여 기각 될 수 있습니다.