Bonjour,
 
J'ai un calcul de complexité à effectuer sur l'algorithme qui test l'égalité de 2 tableaux. J'aurais voulu avoir confirmation du résultat.
 
1. I<-1
2. EGAUX <- T1[I]=T2[I]
3. Tant que ( I != N ) et EGAUX
4.           I<-I+1
5.           EGAUX <- T1[I]=T2[I]  
6. Fin tant que  
 
Meilleur des cas ( T1[1] != T2[1] ) :
1. 1 opération élémentaire
2. 2 opérations élémentaires                                                                                            
3. On a 2 opérations élémentaires que l'on va répéter qu'une fois car le test échoue au premier bouclage
4. 0
5. 0
6. 0  
 
On fait une fois le test dans le tant que donc 2n -> 2 et finalement on obtient 1+2+2 = 5. On obtient donc une complexité en O(1) ?
 
Pire des cas ( T1=T2 )
1. 1 opération élémentaire
2. 2 opérations élémentaires                                                                                           *  . .  . *
3. On a 2 opérations élémentaires que l'on va répéter 2(N-1) + 2 fois. Quand I vaut N on ne fait que les 2 tests élémentaire sans rentrer dans la boucle.
4. 2 opération élémentaires
5. 2 opération élémentaires
6. 0  
 
Donc on a 1 + 2 + 2(n-1)(2+2) + 2 = 8n - 3 soit une complexité en O(n).
 
Ai-je la bonne réponse ? Merci d'avance pour votre aide.

Bonsoir,
On ne considère pas la complexité dans le meilleur des cas (enfin je pense pas).
Sinon oui c'est bien o(n). car pour deux tableaux de n éléments il te faut au plus parcourir ces n éléments pour les comparer.