Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1706 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Calcul de compléxités

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Calcul de compléxités

n°2036122
darkwall_3​7
Posté le 15-11-2010 à 20:35:04  profilanswer
 

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.


Message édité par darkwall_37 le 15-11-2010 à 20:43:43
mood
Publicité
Posté le 15-11-2010 à 20:35:04  profilanswer
 

n°2036150
breizhbugs
Posté le 15-11-2010 à 22:48:38  profilanswer
 

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.


Message édité par breizhbugs le 15-11-2010 à 22:53:00

---------------
Seul Google le sait...

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Calcul de compléxités

 

Sujets relatifs
SML et le lambda calculFaire le calcul de moyenne en Java
Fichier .bat pour calculprobleme de calcul matriciel
[RESOLU][MySQL] calcul suivant le cas ....problème de calcul d'une moyenne en 'double'
URGENT : Calcul AccessCalcul URL relative entre 2 dossiers
Calcul du minimumunicité d'une courbe de HIlbert en 3D a partir du motif initial
Plus de sujets relatifs à : Calcul de compléxités


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR