O (1)에서 nCr 조합 수 찾기

Question

O (1)에서 조합 수 (실제 조합 제외)를 찾을 수있는 방법이 있습니까? 나는 대답을 읽었다 - time and space complexity of finding combination (nCr). 대답은 실제 조합을 찾기 위해 O (n!)가 필요하지만 그러한 조합 수를 찾기 위해 O (1) 만 필요하다는 것입니다. 나는 그것이 어떻게 행해질 수 있는지 이해할 수 없었다. O (1)에서 어떻게하는지 설명해주십시오. 여기서, O (1)은 시간 복잡성이다.

[편집] : 주요 문제는 n을 구현하는 방법입니다! O (1).

Answer 1

조합의 수 (가 아닌 실제 조합)을 찾을 수있는 방법은 O에, 거기에 (1)

예, 숫자 n의 조합 수의 수없이 찾을 수 있습니다 공식 2를 사용하는 반복 ⁿ -1, 공집합 제외.

Answer 2

아래의 C 프로그램을 확인하십시오. 이것은 입력으로서 n 및 r 소요 ^N C 산출 _R 값 :

int main(){ 
    int n, r; 
    scanf("%d", &n); 
    scanf("%d", &r); 

    /* 
    * nCr = n!/!(n-r)/!(r) 
    *  = n * n-1 * n-2 * .... * 1/(n-r * n-r-1 * .. * 1)/
    *   (r * r-1 * ... * 1) 
    *  = n * n-1 * n-2 * n-r+1/(r * r-1 * ... * 1) 
    *  
    */ 

    int result = 1; 
    int i; 

    for (i=0; i<r; i++){ 
     result *= (n-i); // n * n-1 * n-2 * .... * n-(r-1) 
     result /= (i+1); // r * r-1 * ... * 1 
    } 

    /* The loop is going to run only r times for any n 
    * Time to calculate nCr : O(r) 
    * Space complexity: O(1) 
    */ 

    printf("Result of C(%d, %d) = %d", n, r, result); 

    return 0; 
} 

을 계산하는 루프가 단지 'R'번 실행.

따라서, 된 NCR 값을 계산하는 시간 복잡도는 O(r) 이다 그러나 공간의 복잡성은 당신이 두 복잡성 주문과 혼동되어 있어야합니다 생각 O(1)

입니다. 희망, 그것은 당신을 돕는다.

Answer 3

일정 시간에 n!을 계산하려는 경우 스털링의 근사를 사용하지 않는 이유는 무엇입니까?

n! \approx sqrt(2 * pi * n) * (n/e)^n

또는 C에

:

pow(n, n) * exp(-n) * sqrt(2.0 * PI * n);

나는, 그 각 작업의 실제 실행 시간이 아키텍처 의존이 당신에게 일정 시간에 가장 가까운 얻을 것이라 생각합니다.

출처 :

https://en.wikipedia.org/wiki/Stirling%27s_approximation

https://github.com/ankurp/C-Algorithms/blob/master/factorial/fact.c

Answer 4

의 nCr의 실행 시간 복잡도는 O에있을 수 있습니다 (1) 사용하는 컴퓨팅 플랫폼은 N을 계산하는 경우! O (1). 표준 컴퓨터에서는 그렇지 않습니다.

하지만 우리는 특급 (N) 및 로그 (n은) 보통 an O(1) operation for IEEE doubles 및 implement an approximation of log(n!) 사실 사용할 수 있습니다 - 스털링의 근사치에 기반을 - O에 (1) :

logf(n) = log(n!) = (n – 0.5) * log(n) – n + 0.5 * log(2 * PI) + 1/(12 * n) 

우리는 이것을 결합하는 경우 255 ≤ N에 대한 로그 (! n)에 대한 조회 테이블 우리 것입니다 여전히 최소 14 개 유효 숫자를 다음과 같이 우리의 nCr의 아주 좋은 근사값을 계산할 수 있습니다 :

binomial(n, r) = exp(logf(n) - logf(n - r) - logf(r))