Discussion :

[siempre]

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

[Invité(e)]

Bonjour ce que tu cherches à calculer ressemble a la somme des [ame="http://fr.wikipedia.org/wiki/Coefficient_binomial"]combinaisons de k parmi n[/ame], k variant de 2 à n, et n étant le nombre de caractères.

N(4) = C(2, 4) + C(3, 4) + C(4, 4)

On généralise :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
      i = n
      ____
      \    
N(n) = \  C(i, n)
       /  
      /___
     i = 2

Sachant que [cf ici]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
i = n
____
\    
 \  C(i, n)  = 2**n
 /  
/___
i = 0

et que,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
C(0, n) = 1 pour tout n et 
C(1, n) = n pour tout n

On peut en déduire que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

N(n) = 2**n - n - 1

Vérifions qu'on trouve bien le même résultat : n = 4.
16 - 4 - 1 = 11. On retombe sur nos pieds.

[siempre]

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

- O(n*C(n/2,n))

- 2 à la puissance n - n - 1 (comme vous dites)

Est ce que la première est juste ?
Comment on trouve son calcul ?

[Invité(e)]

- O(n*C(n/2,n))
[...]
Est ce que la première est juste ?
Comment on trouve son calcul ?

Je ne sais pas, où as tu trouvé ceci ?

J'ai trouvé deux résultats sur la complexité de toutes les combinaisons de n éléments:
[...]
- 2 à la puissance n - n - 1 (comme vous dites)

Attention, tout ce que j'ai fait, c'est compter le nombre de combinaisons répondant au problème posé.

[siempre]

Bonjour,

Combien coût le code suivant en fonction de nombre d'opérations (complexité) sachant que ce code permet d'afficher toutes les combinaisons de N attributs ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
 
#define N 5
void afficher(int etat[], char *t[])
{
  int i;
  for (i = 0; i < N; i++)
    if (etat[i])
      printf("%s ", t[i]);
  puts("");
}
 
void partie(int h, int etat[], char *t[])
{
  enum { ABSENT, PRESENT };
  if (h < 0)
    afficher(etat, t);
  else
    {
      etat[h] = ABSENT;
      partie(h - 1, etat, t);
      etat[h] = PRESENT;
      partie(h - 1, etat, t);
    }
}
 
int main(void)
{
  char *t[N] = { "nom", "prenom", "age", "adresse", "emploi" };
  int etat[N];
  partie(N - 1, etat, t);
  return 0;
}

[Invité(e)]

On peut l'évaluer à la main.
J'ai repris ton code, mais j'ai supprimé l'affichage et agrandi le tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
25 attributs :
real    0m0.971s
 
26 attributs :
real    0m1.880s
 
27 attributs :
real    0m3.538s
 
28 attributs :
real    0m7.352s

On remarque que quand on ajoute un attribut de plus, le temps de traitement double.
Temps(N+1) = 2 x Temps(N)

-> Temps(N) de la forme O(N**2)