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 ?