AccueilPortailS'enregistrerConnexion

Partagez | 
 

 Qu'est-ce que la complexité O d'un algorithme ?

Aller en bas 
AuteurMessage
sirus
Admin
Admin
avatar

Masculin
Nombre de messages : 286
Age : 30
Réputation : 0
Points : 37
Date d'inscription : 30/05/2008

MessageSujet: Qu'est-ce que la complexité O d'un algorithme ?   Lun 9 Nov - 11:05

La notation grand O est une notation mathématique très utilisée en algorithmique pour permettre de quantifier le nombre de calcul qu'effectue une fonction ou un algorithme.

On utilise parfois la notation Theta pour dire que deux fonctions sont équivalentes. f=Theta(g) est équivalent à dire f=O(g) et g=O(f). On parle souvent de O alors que l'on devrait parler de Theta pour être plus précis.

Exemple avec un algorithme :

En général, on définit une fonction qui réalise quelque chose (par exemple ici, sommer les n premiers entier). On cherche un algorithme qui le résout effectuant un nombre de calcul le plus petit.


Calcul de la somme des n premiers entiers
fonction somme(Entier n) -> Entier
j <- 0
Pour i=1 à n faire
j <- j+i

Retourner j

Ce code effectue n somme (en considérant que l'incrémentation de i n'est pas une somme), c'est un algorithme en O(n).

On aurait également pu calculer la somme directement avec la formule bien connue :


Calcul de la somme des i premiers entiers
fonction somme(Entier n) -> Entier
Retourner (n+1)n/2


Si la multiplication se fait en temps constant (comme c'est le cas sur les processeurs actuels en général, car on considère les entiers bornés), l'algorithme effectue 1 somme, une multiplication et une division, il est en O(1) = 3 opérations.

Ainsi, on a un exemple d'une fonction admettant deux algorithmes qui la détermine, mais de complexités différentes.
Revenir en haut Aller en bas
 
Qu'est-ce que la complexité O d'un algorithme ?
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
 :: Vision Sur l'Université :: Informatique :: Département Informatique LMD :: 2éme Année :: Algorithmique et Stucture de Données-
Sauter vers:  
Creer un forum | © phpBB |  | Contact | Signaler un abus