Dynamic Programming - The Binomial Coefficient

3.1 The Binomial Coefficient

nCk 라고 배웠다.

standard notation은 (nk) 라고 쓴다. 위.

n개의 물건 중 k개를 선택하는 방법.

 

시간이 오래걸린다.

계속 중첩돼서 값을 구해야 하기 때문에 오래 걸린다. 

했던 일 또하고 또하고 또하고

recursive call 일어나는 횟수를 세면 2 * nCk - 1 이다. 이게 시간복잡도이다.

n값이 고정되어 있더라도 k값이 변한다.

 

k값이 n/2일 때 값이 가장 크다.

Algorithm 3.1의 시간복잡도가 나쁘다는 것을 알 수 있다.

 

그러면 어떻게 하냐?

B라는 2차원 배열을 만들어서

i값은 0부터 n까지

j값은 0부터 k까지

 

 ㄱ 형태로 더하면서 채운다.

맨아래쪽의 ㄱ 아래 값을 return 하면 된다.

 

시간 복잡도는 채워야 되는 빈 칸의 개수에 비례한다. n*k 의 절반 쯤 된다.

O(n * k) 

 

O(2^n / sqrt(n)) 과 비교해보면 하늘과 땅 차이다.

 

따라서 일반적으로 Binomial Coefficient 하려면 Algorithm 3.2를 쓰는게 맞다. 효율성 때문에.

recurrsion으로 구현하지말고 배열을 써서 iteration으로 배열을 채워나감으로써 구현하자.

 

단점은 memory를 많이 쓴다.