le calcul de la complexité

Bonjour,
Quelle est la complexité au pire de cas pour le calcul de toutes les combinaisons possibles pour n caractères à partir de taille 2 jusqu'à la taille n ?

Prenons par exemple 4 caractères:a, b, c et d Toutes les combinaisons possibles sont:

- les combinaisons de taille 2 sont: ab, ac, ad, bc, bd, cd //ici on a 6 combinaisons

- les combinaisons de taille 3 sont: abc, abd, acd, bcd //ici on a 4 combinaisons

- les combinaisons de taille 4 sont: abcd //ici on a 1 combinaison

Merci

Bonjour,

[ Lien ]


pour faire simple
factoriel(nombre de caractère)
--------------------------------
factoriel (taille) * factorielle(nombre de caractère - taille)

dans ton cas on a
4! / (2!*(4-2)! = (4*3*2)/(2*2) = 6
4! / (3!*(4-3)! = (4*3*2)/(3*2) = 4
4! / (4!*(4-4)! = (4*3*2)/(4*3*2) = 1

J'ai trouvé deux résultats sur la complexité de toutes les combinaisons de n éléments:

- n*C(n/2,n)

- 2 à la puissance n

Laquelle est juste ou les deux sont fausses ?

houla, mon dernier calcul de complexité ca doit remonter à une dizaine d'années.

la première me semble pas mal puisque c'est n combinaisons, quoique j'aurais tendance à dire qu'il y a n-1 combinaison.
mais je ne pense pas pouvoir t'aider plus, dsl

Juste un question : t'entends quoi par "complexité" ? en général, c'est pour déterminer la faisabilité ou la rapidité de convergence, non ?

La complexité pour moi est le nombre des opérations effectués.