Discussion :

[saffou]

Salut à tous,

En fait, j'ai trouvé deux façon de calculer la Combinaison de p éléments parmi n, et je me demande lequel est meilleur de point de vue complexité en temps et en espace et pourquoi. Voici les deux algorithmes:

**********1ère méthode***********
Comb_1(n,p: entier): réel
Si (p=n) Alors Comb_1← 1
Sinon Si (p=1) Alors Comb_1 ← n
Sinon Comb_1← (n/p)*Comb_1(n-1,p-1)
Fin Comb_1

**********2ème méthode***********
Comb_2(n,p: entier): réel
Si ((p=0) ou (p=n)) Alors Comb_2← 1
Sinon Comb_2←Comb_2(n-1,p)+Comb_2(n-1,p-1)
Fin Comb_2




Merci Bcp

[Zavonen]

Le second est récursif double, et le premier est simple.
Donc a priori le premier est meilleur.
MAIS il fait intervenir des divisions... donc risque d'arrondis.
Il y a déjà eu une (au moins) discussion là-dessus. Il existe des algos itératifs.