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)

[siempre]

Merci beaucoup.


J'ai trouvé une solution permettant de supprimer des lignes vides et des colonnes vides de fichier.
Voici le lien de cette solution:
http://groups.google.fr/group/fr.com...61b1a577ad0eaf

Exemple de fichier "entree.txt":

12 11001
15 01100
21 10001
23 00000
13 00101

Nous obtenons le fichier "sortie.txt":

12 1101
15 0110
21 1001
13 0011

Le fichier de position de colonnes supprimées "position.txt":

3

3 c'est la position de colonne supprimée si on compte à partir de 0.

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
int enlever_lig_col(int *nbAF,int *nbAFS,int *nbAFNS)
{
 FILE *pFile, *pFileOut,*pCol,*fp, *fpAttF, *fp_cause,*fpNS;
	char sLine[MAXLINE], s[100],t[100], ch[100], type[10], attribut[20], comparateur[10],valeur[20];
    int i,j,h=0,k=0,nColumn[32] = {0}, nCpt = 0, nAttribLength= 0, nMaxAttribLength = 0;
    int dataTabStringMax = STEP;
	int nShift = 0,nbA=0,nbAS=0,nbANS=0;
	int vv,pos,nbO=0;
    dataStruct *dataTabString;  
      pFile = fopen("entree.txt","r");
    pFileOut = fopen("sortie.txt","w+");
    pCol = fopen("position.txt","w+");
 
        if (pFile && pFileOut)
        {
                dataTabString = (dataStruct *) malloc(dataTabStringMax * sizeof(dataStruct));
 
                while (fgets(sLine, MAXLINE, pFile))
                {
 
					memset(&dataTabString[nCpt], 0, sizeof(dataStruct));            
					sscanf(sLine,"%d%s",&dataTabString[nCpt].sNum,dataTabString[nCpt].sAttrib);
							if (strlen(dataTabString[nCpt].sAttrib) > 0) 
							nAttribLength = strlen(dataTabString[nCpt].sAttrib)+ 1;
 
                        if (nAttribLength>0)
                        {
 
						sscanf(sLine,"%d%s",&dataTabString[nCpt].sNum,dataTabString[nCpt].sAttrib);
							for (i = 0; i<nAttribLength; i++)
                                {
                                        if (dataTabString[nCpt].sAttrib[i] == '0')
                                                nColumn[i]+=1;
                                }
                                nCpt+=1;
                                if (nAttribLength > nMaxAttribLength)
                                        nMaxAttribLength = nAttribLength;
                        }
                        if (nCpt == dataTabStringMax)
                        {
                                dataTabStringMax += STEP;
                                dataTabString = (dataStruct *) realloc(dataTabString,
                                        dataTabStringMax * sizeof(dataStruct));
                                if (dataTabString == NULL)
                                        exit(1);
                        }
                }
 
 
 
                // Lecture tableau de structures pour supprimer les "0"
                for (j = 0; j<nCpt; j++)
                {
 
						 nShift = 0;
                        for (i = 0; i<nMaxAttribLength; i++)
                        {
                                if (nColumn[i] == nCpt)
                                {
                                        memmove(&dataTabString[j].sAttrib[i-nShift], &dataTabString[j].sAttrib[i-nShift+1], strlen(&dataTabString[j].sAttrib[i-nShift+1]) + 1);
                                        nShift+=1;
										if (j == 0)
										{
										//printf("pos = %d\n",i);
										fprintf(pCol,"%d\n",i);
										}
                                }
                        }
                        if (strcspn (dataTabString[j].sAttrib, "1") <strlen(dataTabString[j].sAttrib))
 
						{
					  fprintf(pFileOut, "%d %s\n", dataTabString[j].sNum,dataTabString[j].sAttrib);
 
					 nbO++;
 
						}
                }
 
 
                free(dataTabString);
 
	}
}

- Pouvez vous me détailler encore étape par étape cette solution ?

- Que présentent les deux variables de deux boucles for : nCpt et
nMaxAttribLength ?

- quelle est le rôle de la fonction memmove() et memset() ?

Quelle est la complexité de cette solution ?

Merci.

[Invité(e)]

Merci beaucoup.


J'ai trouvé une solution permettant de supprimer des lignes vides et des colonnes vides de fichier.
Voici le lien de cette solution:
http://groups.google.fr/group/fr.com...61b1a577ad0eaf

Quel rapport avec la première question ?

- Pouvez vous me détailler encore étape par étape cette solution ?
- Que présentent les deux variables de deux boucles for : nCpt et
nMaxAttribLength ?
- quelle est le rôle de la fonction memmove() et memset() ?

Il faudrait mieux poser ces question sur le forum C.
Voir les pages man pour le détails des fonctions memmove et memset.

Quelle est la complexité de cette solution ?

Tu peux faire comme j'ai fait pour le code précédent : augmenter petit à petit les entrées et tenter d'y voir une loi.

[siempre]

Bonjour,

Quel rapport avec la première question ?

J'ai utilisé cette solution dans mon travail. Je voulais savoir la complexité cette solution.

Il faudrait mieux poser ces question sur le forum C.

J'ai déjà déposé ce code mais pas de réponse.
Voici le lien:
http://www.developpez.net/forums/d90...ntenu-fichier/

Tu peux faire comme j'ai fait pour le code précédent : augmenter petit à petit les entrées et tenter d'y voir une loi.

Comment vous savez à partir de mesure de temps, la valeur exacte de la complexité d'un tel code ? et comment vous choisissez les paramètres de mesure ?

Merci.

[Invité(e)]

J'ai déjà déposé ce code mais pas de réponse.

Un peu de lecture : http://club.developpez.com/regles/#L4.7.

Tu peux faire comme j'ai fait pour le code précédent : augmenter petit à petit les entrées et tenter d'y voir une loi.

Comment vous savez à partir de mesure de temps, la valeur exacte de la complexité d'un tel code ? et comment vous choisissez les paramètres de mesure ?

Ce n'est pas trivial.

Le paramètre de mesure est la taille des données en entrée.

Dans ton cas, tu as un tableau de taille NxN.

Tu pourrais tester ton algo avec des tableaux que tu construis toi même.
Il faut que la taille du tableau soit suffisamment grande pour que l'execution dure assez de temps pour pouvoir négliger les temps de latences qui ne dépendent pas du tableau lui même (chargement du programme, thread d'arrière plan du PC...).

Avec les temps d'exécution en fonction de N, tu peux tracer une courbe avec excel et calculer différentes courbes de tendance pour voir laquelle colle le mieux.

Cette solution n'est pas optimale, mais permet d'avoir une idée de la complexité.

Dans le cas précédent, nous avions une idée de la complexité. Le calcul a permis de la vérifier, non de la mesurer.