le calcul de la complexité

Version imprimable

09/04/2010, 15h50
siempre

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
09/04/2010, 16h46
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:

1 2 3 4 5 6 7 i = n ____ \ N(n) = \ C(i, n) / /___ i = 2
Sachant que [cf ici]
Code:

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

1 2 C(0, n) = 1 pour tout n et C(1, n) = n pour tout n
On peut en déduire que

Code:

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.
09/04/2010, 18h49
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 ?
13/04/2010, 12h02
Invité(e)

Citation:

Envoyé par siempre

- 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 ?

Citation:

Envoyé par siempre

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é.

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:

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;
}

13/04/2010, 18h08
Invité(e)
On peut l'évaluer à la main.
J'ai repris ton code, mais j'ai supprimé l'affichage et agrandi le tableau :
Code:

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)

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":

Citation:

12 11001
15 01100
21 10001
23 00000
13 00101

Nous obtenons le fichier "sortie.txt":

Citation:

12 1101
15 0110
21 1001
13 0011

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

Citation:

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

Code:

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.

14/04/2010, 12h01
Invité(e)

Citation:

Envoyé par 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

Quel rapport avec la première question ?

Citation:

Envoyé par siempre

- 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.

Citation:

Envoyé par siempre

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.
15/04/2010, 08h00
siempre

Bonjour,

Citation:

Quel rapport avec la première question ?

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

Citation:

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/

Citation:

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.
15/04/2010, 10h21
Invité(e)

Citation:

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

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

Citation:

Citation:

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.