Discussion :

[tipi_11]

Bonjour j'ai un problème de complexité :

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int count (int *T, int n)
{
   int j;
   if (n == 0)
      return 0;
   j = 1;
   while ((n-1-j >= 0) && (T[n-1-j] != T[n-1]))
      j = 2*j;
   if (n-1-j >= 0)
      return count(T, n-1);
return (count(T, n-1)+1);
}

Donc dans le pire des cas la boucle while sera effectué (n-1)*(n-2) fois. n-1 fois pour l'itération et n-1-j fois pour l'itération de while ? D'ou en minorant j par 1.

D'ou T(n) = n*T(n-1) D'ou une complexité polynomiale.

[Matt_Houston]

C'est de l'algorithmique plus que du C.

Quelle est ta question exacte ? Qu'est sensée faire cette fonction ? Pré- et post-conditions, description, commentaires, tout ça...

[tipi_11]

Lorsque je parle de complexité je parle de complexité de temps dans le pire des cas, donc du nombre d'operation dans le pire des cas.

Je cherche a calculé le nombre de fois que sera effectué la boucle while dans le pire des cas. Et l’équation récursive qui décrit
le nombre d’opération élémentaire T(n) effectuée par la fonction count() dans le pire des cas.

Soit si j'ai bien compris la fonction count recherche tous les éléments qui qui sont égaux à la dernière case du tableau.
Et elle se déplace de 2^i allant de i allant de 1 a n. Et renvoie +1 lorsque lors la dernière itération avant de sortir de la boucle, n-1-j est négatif.

Cette fonction est plus une suite d'opération que d'un programme avec un but précis.

Et donc dans le pire des cas T(n) = n*T(n-1) d'ou la complexité polynomiale mais c'est assez compliqué habituellement d'établir la complexité et la l'exercice semble à porter.

Je vous remercie

[dalfab]

Donc dans le pire des cas la boucle while sera effectué (n-1)*(n-2) fois.

Je n'y comprends pas grand chose en algorithmique, ce que je vois:
Pour un N donné, le test de sortie est N-1-J>=0 avec J qui double à chaque itération.
Les valeurs successives du test sont donc : N-1-1, N-1-2, N-1-4, .., .., N-1-2^(x+1) , avec x nb d'itération du while.
Elle s'arrête pour x tel que : N-1-2^(x+1) >= 0, qui devrait se résoudre.

Quant à la fonction, à chaque itération on passe de n à n-1, donc elle est appelée n+1 fois.

Je vois donc un algorithme en au plus n*log(n)

[tipi_11]

Merci

D'ou T(n) = C1 + log(n-1) + T(n-1) donc on peut penser a une complexité o(nlog(n)) ou C1 est le temps de l'operation n == 0;

Si quelqu'un a la demonstration rigoureuse =-)

[souviron34]

ta boucle s'arrêtera au maximum grâce à la condition (n-1-j >= 0)

avec un indice croissant en 2^j

J'aurais donc tendance à dire que cette fonction est en log(n)...


Exemple :

• n = 100
  
  j = 1, 2, 4, 8, 16, 32, 64, 128 => FINI
  
  8 tours
  
  
• n = 1000
  
  j = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 => FINI
  
  12 tours
  
  
• n = 10000
  
  j = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 , 2048, 4096, 8192, 16384 => FINI
  
  16 tours

donc entre 100 et 10000 on a élevé n au carré et on a fait juste 2 fois plus de boucles..