如何计算二项式系数时间和空间的复杂性？ （迭代与递归）

Question

这是迭代版本，但它调用递归函数。这会对其时间/空间复杂性产生影响吗？

int factorial(int n) { 
    if (n == 1) { 
     return 1; 
    } 
    else { 
     return n * factorial(n - 1); 
    } 
} 

int binomial_coefficient_iterative(unsigned int n, unsigned int k) { 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return (factorial(n)/(factorial(k) * factorial(n - k))); 
    } 
} 

这是递归版本，使用C（N，K）= C（N-1，K）+ C（N-1，K-1）式算出。

int binomial_coefficient_recursive(unsigned int n, unsigned int k){ 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return binomial_coefficient_recursive(n - 1, k) + binomial_coefficient_recursive(n - 1, k - 1); 
    } 
} 

最后但并非最不重要的，可以通过你用C计算二项式系数C（N，K）（N，K-1）？

Answer 1

这两个解决方案都取决于递归。在第一个版本中，您可以用简单的迭代来替换阶乘的递归调用。

但是，在第二种解决方案中存在重新计算重叠子问题的问题。

C(n, k) = C(n-1, k) + C(n-1, k-1) 

您应该使用记忆化缓存C（N，K）时，它的计算存储值，当函数具有相同parameteres不是重新计算，查找调用和返回值的值。

在第一个问题中，您正在多次调用可以避免的阶乘函数。该策略是计算增量变化。例如，当计算factorial(k)时，可以导出

factorial(n) = factorial(k) * K+1 * K+2 ...n 

这样可以减少您正在进行的乘法运算的次数。

回到问题的时间复杂性。

1：时间复杂度为O（n），这里为3因子叫你正在做的N，K和NK乘法

第二：这将是

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)   
    where T(n,n) = T(n,0) = O(1) 

解决这个差分方程，你会得到T（n）= O（2^n），（用于查找斐波那契数列的复杂性的相同参数）

所以后面的方法是指数性的，可以使用记忆来降低。