如何計算二項式係數時間和空間的複雜性？ （迭代與遞歸）

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），（用於查找斐波那契數列的複雜性的相同參數）

所以後面的方法是指數性的，可以使用記憶來降低。