求O组中的组合数nCr（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作为输入并计算nCr值：

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 2

如果你试图在恒定时间内计算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 3

如果您使用的计算平台计算n，nCr的运行时复杂度只能在O（1）中！在O（1）。在标准计算机上，情况并非如此。

但是我们可以使用exp（n）和log（n）通常是an O(1) operation for IEEE doubles和implement an approximation of log(n!)的事实 - 基于Stirling的近似 - 在O（1）中：

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

如果我们将这个与log（n！）的查找表结合起来，对于n≤255，我们仍然会有至少14个有效数字，我们可以计算出非常好的nCr近似值，如下所示：

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

Answer 4

Ajeet's answer应该被接受，但我认为它可以改进到Min(O(r),O(n-r))，如果减少仍然是O(r)。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System. in );
        int n = sc.nextInt();
        int r = sc.nextInt();
        // choose smaller one
        if (n - r < r) { 
            r = n - r;
            System.out.printf("Change %d to %d\n", n - r, 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;

        for (int 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 or (n-r) times for any n Time to calculate nCr : Min ( O(r) , O(n-r) )
         * Space complexity: O(1)
         */
        System.out.printf("Result of C(%d, %d) = %d", n, r, result);
    }
}

Answer 5

有没有办法找到O（1）中的组合数（不是实际组合）

是的，您可以使用公式2n-1找到不重复的数字n的组合数量，不包括空集。