Si dans le même algorithme vous décidez de faire une seconde boucle dans la première, pour afficher par exemple une 
table de multiplications : la première boucle va toujours de 1 à n, la seconde va aussi de 1 à n. Au total vous obtenez n 
fois  n  boucles,  donc  n 2   boucles.  La  complexité  est  donc  f(n)= n 2 ,  et  vous  la  noterez  O(n 2 ).  Le  coût  de  l’algorithme 
augmente au carré du nombre d’informations. 
Si vous rajoutez en plus une quelconque opération dans la première boucle, cette opération a aussi un coût que vous 
pouvez  tenter  de  prendre  en  compte.  Si  vous  ajoutez  une  multiplication  et  que  celle­ci  a  un  coût  de  1,  alors  la 
complexité finale est de n*(n+1) soit n 2 +n. Cependant si vous faites une courbe pour de grandes valeurs de n et que 
vous  comparez  avec  la  courbe  simple  n 2 ,  vous  remarquerez  que  le  rajout  devient  négligeable.  Au  final,  l’algorithme 
conserve une complexité O(n 2 ).  
Si la complexité peut parfois être calculée assez finement, il en existe plusieurs "prédéfinies": 
q O(1): complexité constante 
q O(log(n)): complexité logarithmique 
q O(n): complexité linéaire 
q O(n.log(n)): complexité quasi­linéaire 
q O(n 2 ): complexité quadratique
 
q O(n 3 ): complexité cubique
 
q O(n p ) : complexité polynomiale
 
q O(n log(n) ): complexité quasi­polynomiale
 
q O(2 n ): complexité exponentielle
 
q O(n!): complexité factorielle 
Ces complexités ne sont pas forcément faciles à appréhender, aussi voici un graphique représentant quelques unes de 
celles­ci. En abscisse est indiqué le nombre de données à traiter et en ordonnée la complexité associée: le nombre 
d’opérations  effectuées  pour  n  données.  Pour  des  complexités  d’ordre  O(2 n )  l’algorithme  effectue  déjà  1024 
opérations, et plus de 3,5 millions pour O(n!)! 
- 5 -
© ENI Editions - All rigths reserved - Jonifar lina
13