précédent | suivant | table des matières

Complexité : Coefficients du binôme

(application)

Les cefficients du binôme sont définis par la récurrence :

Programmation récursive

Une fonction récursive qui calcule ces coefficients est : 

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

Le temps de calcul de cette fonction est proportionnel au nombre d’appels de la fonction : ce nombre d’appels est donné par la récurrence :

On montre par récurrence que

Les temps de calcul les plus longs sont donc quand k≈n/2 et donc dans ce cas :  : on a alors : ( on utilise la formule de Stirling )


Triangle de pascal

Le coût de la programmation précédente est du au multiples calculs de la même valeur de . Pour minimiser ce coût on peut utiliser une technique de programmation dynamique qui consiste à stocker les valeurs intermédiaires pour ne pas les re-calculer : c’est le triangle de Pascal.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
21 35 35 21
28 56 70 56 28

Pour calculer il suffit de remplir le tableau au rang n ; on a donc un coût proportionnel à .

long binome2( int n, int k){
   long [][] t = new long[n+1][];

for(int i=0; i<=n; ++i){ t[i] = new long[i+1]; t[i][0] = 1; for( int j = 1; j<i; ++j) t[i][j] = t[i-1][j] + t[i-1][j-1]; t[i][i] = 1; } return t[n][k] ; }

Exemple : la fonction caractéristique de la loi Γ tronquée est définie par : 

pour et 0 sinon

Ecrire une programmation récursive, et donner une idée de solution utilisant la technique du triangle de Pascal.

haut de la page