Discussion :

[souviron34]

Bonjour à tous..

Je viens vous demander un coup de main pour une question de vocabulaire..

Comment qualifie-t-on la complexité en termes de nombre d'opérations ?

(en supposant qu'on ne prenne pas (à moins que la définition ne l'exige) le nombre d'opérations élementaires)


Exemple :

j'ai un algo qui fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
pour i = 0 jusqu'à i < N
   ...
fin pour
 
pour i = 0 jusqu'à i < N
   ...
fin pour
 
pour i = 0 jusqu'à i < N
   ...
fin pour

Sa complexité sera en O(N)..

Mais si maintenant je trouve un moyen de le faire avec une seule boucle :

Code :

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

1
2
3
pour i = 0 jusqu'à i < N
   ...
fin pour

Sa complexité sera toujours O(N), mais comment appelle-t-on l'optimisation ainsi faite ? En gros, comment appelle-t-on le nombre d'opérations nécessaires pour effectuer un algo, même sans changer sa complexité intrinsèque..





PS: pour confirmation sur un autre sujet proche, si j'ai :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
M = 3
 
pour i = 0 jusqu'à i < N
   pour j = 0 jusqu'à j < M
      ....
   fin pour
 
   si condition
      alors M = M + 1
   fin si
fin pour

la complexité sera bien O(N*log(M)), non ?

[b_reda31]

Bonjour,
J'espère ne pas dire n'importe quoi :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
M = 3
pour i = 0 jusqu'à i < N
   pour j = 0 jusqu'à j < M
      ....
   fin pour

   si condition
      alors M = M + 1
   fin si
fin pour

la complexité sera bien O(N*log(M)), non ?

Il me semble que dans le meilleur des cas, c'est à dire lorsque condition n'est jamais vérifiée la complexité serait en O(NM) (qui est supérieur à O(N*log(M))) ; et dans le pire des cas (condition toujours vérifiée ), l'algorithme ne se terminera jamais.
ou peut être qu'il s'agit d'une décrémentation de M si la condition est vérifiée au lieu d'une incrémentation?

[souviron34]

Bonjour,
J'espère ne pas dire n'importe quoi :


Il me semble que dans le meilleur des cas, c'est à dire lorsque condition n'est jamais vérifiée la complexité serait en O(NM) (qui est supérieur à O(N*log(M))) ; et dans le pire des cas (condition toujours vérifiée ), l'algorithme ne se terminera jamais.
ou peut être qu'il s'agit d'une décrémentation de M si la condition est vérifiée au lieu d'une incrémentation?

je ne crois pas...

Dans le pire des cas (condition toujours vérifiée) M = N + 3, donc l'algo non seulement se termine, mas la complexité est O(N^2), mais pour le dernier tour de boucle seulement..

Dans le le meilleur des cas, c'est O(N), puisque le facteur constant 3 n'est pas pris en compte dans le calcul de la complexité..

Mais dans la moyenne, M croît d'une valeur de départ 3 jusqu'à une valeur d'arrivée Mf..

Je crois bien que c'est O(N log(M)) la formule.. car M croît au fur et à mesure..

[b_reda31]

Effectivement, j'avais tout faux. Mille Excuses Souviron

[pseudocode]

Mais si maintenant je trouve un moyen de le faire avec une seule boucle :

Sa complexité sera toujours O(N), mais comment appelle-t-on l'optimisation ainsi faite ? En gros, comment appelle-t-on le nombre d'opérations nécessaires pour effectuer un algo, même sans changer sa complexité intrinsèque..

Dans ton cas, je suppose que la complexité cyclomatique est la mieux adaptée (on passe de 3 boucles à 1 seule). Cela fait partie des métriques de code que l'on utilise généralement.

la complexité sera bien O(N*log(M)), non ?

Bah, heu... au pire M=N+3, donc c'est en O(N²).

En moyenne, tout dépend de la condition.

[souviron34]

Bah, heu... au pire M=N+3, donc c'est en O(N²).

j'ai du mal avec ça...

Car M=N+3 au dernier tour de boucle...

Admettons que la condition soit remplie à tous les coups...

On a en fait l'équivalent d'un développement :

1*3 + 1*4 + 1*5 + ..... + 1*(N+2) = ... * N

J'ai beaucoup de mal à dire que ceci est identique à :

1*N + 1*N + .... + 1*N = N * N

Car M ne vaut N qu'à la fin...

Jusqu'à N/2, M < N/2
de N/2 à N, N/2 < M < N

Pour moi ça ressemble fortement au développement de Taylor d'un log...





Sinon merci pour le "cyclomatique".. Je vais regarder... Et sinon, comment ça s'appelle quand on compte les opérations élémentaires ? et dans ce cas comment faut-il compter ? la mise en registre compte-elle ? comment compte un sqrt de double ?

[Nebulix]

1+2+3+...+n=n*(n-1)/2 ~O(n²)

[souviron34]

ok merci...

Le lycée est loin et je n'ai pas touché les développements depuis... Je ne me souvenais plus de la formule..

Donc j'admet mon erreur...

Merci et désolé de l'ncompréhension, pseudocode ...

[pseudocode]

ok merci...

Le lycée est loin et je n'ai pas touché les développements depuis... Je ne me souvenais plus de la formule..

Donc j'admet mon erreur...

Merci et désolé de l'ncompréhension, pseudocode ...

Oh, ce n'est rien. J'ai été un peu léger dans mes explications. Heureusement que Nebulix à compris mon esprit tortueux.

Comme on ne connait pas grand chose sur la condition, on ne peut pas évaluer une complexité moyenne. La complexité "worst case" n'est qu'un indicateur.

Si le "worst case" n'arrive que 1 fois sur N! (comme c'est le cas du quicksort), alors ce n'est pas très représentatif.