c - 查找组合数 nCr，时间复杂度为 O(1)

Question

有没有办法在 O(1) 内找到组合的数量(不是实际的组合)？我在这里读到一个答案 - time and space complexity of finding combination (nCr) 。答案是需要 O(n!) 来找到实际的组合，但只需要 O(1) 来找到这样的组合的数量。我不明白这是怎么做到的。请解释一下如何在 O(1) 内做到这一点。这里，O(1)是时间复杂度。

[编辑]:我遇到的主要问题是如何实现 n!时间复杂度为 O(1)。

Answer 1

请检查下面的C程序。它以 n 和 r 作为输入并计算 ⁿC_r 值:< br/>

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)

我想您一定对这两个复杂度顺序感到困惑。希望对您有帮助。