Version imprimable
Bonjour j'ai un problème de complexité :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
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.
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...
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
Je n'y comprends pas grand chose en algorithmique, ce que je vois:Citation:
Envoyé par tipi_11
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)
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 =-)
ta boucle s'arrêtera au maximum grâce à la condition (n-1-j >= 0)
avec un indice croissant en 2j
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..
:D