재귀 조합 시간 복잡도 분석

Question

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

Answer 1

이 T(a,b)이 C(a,b)C(n,k)의 재귀 호출 트리에 호출되는 함수 횟수하자 T (N)의 재귀 이항 계수의 지수 시간 복잡도에 대한 설명 . 이 C(a+1,b)과 C(a+1,b+1)에서 호출되기 때문에 (이 중 하나를 호출 할 때마다) T(a,b)=T(a+1,b)+T(a+1,b+1)이됩니다. 이것은 Pascal's triangle formula이다 재귀 호출 트리 마지막 레벨 T들 파스칼 삼각형 n 번째 레벨을 형성하고, 따라서 n (예 k=n/2 이처럼, 에지 경우 예 k=1 또는 k=n를 금지.)으로 지수이다.

cache the results 경우 알고리즘 O(n*k) 시간을 만들 수 있습니다.