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.
Lun 9 Nov - 11:05
