Binomial Coefficient (이항 계수)

- 정의

(x+1)^n 의 항을 전개했을 때, x^k항의 계수가 C(n, k)로 표현된다.

n개의 항목 중 k개를 순서를 고려하지 않고 선택하는 경우의 수로도 잘 알려져 있다.

 

- Pseudocode

// Iterative way (Dynamic programming)
public static int binDP (int n, int k) {
    index i, j;
    int[][] B = new int[0..n][0..k];
    
    for (i=0; i<=n; i++)
        for (j=0; j <= min(i, k); j++)
            if (j==0 || j==i) B[i][j] = 1;
            else B[i][j] = B[i-1][j-1] + B[i-1][j];
    
    return B[n][k];
}

// Recursive way (Divide and conquer)
public static int binDC (int n, int k) {
    if (k==0 || k==n) return 1;
    return binDC(n-1. k-1) + binDC(n-1, k);
}

dp를 이용한 방법은 2차원 배열을 이용한 Bottom-up 방식을 사용하여 계산한 것이다.

또한, j <= min(i, k)를 반복문에서 사용하여 배열의 값을 계산하는 범위를

lower triangle 범위로 한정지어서 최적화 한다.

 

Divide and Conquer를 이용한 방식은 앞서 많이 봤던대로 재귀 함수를 호출하는 방식이다.

 

- Time complexity (dp)

Basic Operation: an assignment of B[i][j]

Input Size: n, k (n > k)

 

* Every case:

[Θ(nk)]

 

- Time complexity (dc)

Basic Operation: return of binDC

Input Size: n, k

 

* Every case: T(n, k) = 2C(n, k) - 1 [Θ(n!/k!)]