Comment calculer le temps du coefficient binomial et la complexité de l'espace? (itérative vs récursive)

Question

Ceci est la version itérative, mais elle appelle une fonction récursive. Cela aurait-il un effet sur la complexité de son temps/espace?

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))); 
    } 
} 

Ceci est la version récursive, calculé en utilisant la C (n, k) = C (n-1, k) + C (n-1, k-1) formule.

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); 
    } 
} 

Last but not least, vous pouvez calculer le coefficient binomial C (n, k) en utilisant C (n, k-1)?

Answer 1

La solution dépend de la récursivité. Dans la 1ère version, vous pouvez remplacer l'appel récursif de factoriel par une itération simple.

Cependant, il existe un problème de recalcul des sous-problèmes qui se chevauchent dans la 2ème solution.

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

Vous devez utiliser memoization pour mettre en cache les valeurs de C (n, k) chaque fois qu'il est calculé stocker la valeur et lorsque la fonction appelle les mêmes parameteres au lieu re calcul, la recherche et retourner la valeur.

Dans le premier problème, vous effectuez plusieurs appels à la fonction factorielle qui pourraient être évités. La stratégie consiste à calculer le changement incrémentiel. Par exemple, lorsque vous calculez factorial(k) vous pouvez tirer

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

Cela réduit le nombre de multiplication que vous faites.

Pour en revenir à la complexité de l'espace-temps du problème.

1er: complexité est en O (n) ici pour 3 factoriel appels que vous faites n, k et la multiplication nk

2: Ce sera

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

Résoudre cette équation de différence entre vous obtenir T (n) = O (2^n), (même argument utilisé pour trouver la complexité de la série fibonacci)

Donc l'approche ultérieure est exponentielle qui peut être réduite en utilisant la mémoisation.