Complexité en temps
La complexité en temps représente de façon asymptotique le temps que met un algorithme à trouver une solution.
Opération élémentaire
La complexité consiste à évaluer l’efficacité de la méthode M et de comparer cette dernière avec une autre méthode M’. Cette comparaison est indépendante de l’environnement (machine, système, compilateur, langage, etc). L’efficacité dépend du nombre d’opérations élémentaires. Ces dernières dépendent de la taille des données et de la nature des données.
Dans le cas d’une structure de type séquence, l’évaluation est égale à la somme des coûts. Par exemple, si l’algorithme possède un traitement T1(n) suivit de T2(n), alors T(n)=T1(n)+T2(n).
Dans le cas d’un embranchement, l’évaluation est égale au maximum des embranchements. Par exemple, l’algorithme exécute T1(n) sinon T2(n), alors T(n)=max(T1(n), T2(n)).
Dans le cas d’une boucle, l’évaluation est égale à la somme des coûts des passages successifs. Par exemple, si l’algorithme est un « tant que faire Ti(n) avec la complexité de Ti(n) dépendant du numéro i de l’itération. Alors la complexité est T(n) = somme(i=1 à n) Ti(n).
Notation de Landau
la notation de Landau caractérise le comportement asymptotique d’une fonction, c’est à dire le comportement de f(n) quand n tend vers l’infini.
Exemples
Pire, meilleur et moyenne
Considérons un algorithme de recherche d’un élément dans un tableau en forme itérative. L’algorithme s’arrête lorsque la valeur a été trouvée. L’algorithme se décompose ainsi : affectation de 0 à i, tant que i n’a pas parcouru le tableau on incrémente i, si tab[i]=valeur alors on retourne vrai, sinon à la fin du tableau on retourne faux. Notons C la complexité du corps de la boucle.
Au pire des cas, l’algorithme parcours tout le tableau, c’est à dire que T(n)=1+n*C=O(n). Au mieux, l’élément est au début du tableau, donc T(n)=1+C=O(1). Nous considérons qu’en moyenne, il y a 50% de chance que l’élément ne soit pas dans le tableau, et 50% qu’il soit à la moitié du tableau (ceci est bien entendu absurde, mais nous ne ferons pas toutes les possibilités). Dans ce cas, la complexité en moyenne est de T(n)=0.5*(1+n*C)+0.5*(1+n*C/2)=a*n+b avec a et b des constantes = O(n). Nous remarquons que le comportement asymptotique en moyenne est le même qu’au pire cas.
Exemples
Supposons que chacune des expressions ci-dessous donne le temps de traitement T(n) passé par un algorithme pour résoudre un problème de taille n. Sélectionnez le terme dominant (s) ayant la plus forte augmentation de n et spécifiez la complexité Big-Oh la plus basse de chaque algorithme.
| Expression | Dominant | O(.) |
| 5 + 0.001n3+ 0.025n | 0.001n3 | O(n3) |
| 500n + 100n1.5 + 50n log10 n | 100n1.5 | O(n1.5) |
| 0.3n + 5n1.5 + 2.5 n1.75 | 2.5 n1.75 | O(n1.75) |
| n2 log2 n + n(log2 n)2 | n2 log2 n | O(n2 log n) |
| n log3 n + n log2 n | n log3 n, n log2 n | O(n log n) |
| 3 log8 n + log2 log2 log2 n | 3 log8 n | O(log n) |
| 0. 100n + 0.01n2 | 0.01n2 | O(n2) |
| 0.01n + 100n2 | 100n2 | O(n2) |
| 2n + n0.5 + 0.5n1.25 | 0.5n1.25 | O(n1.25) |
| 0.01n log2 n + n(log2 n)2 | n(log2 n)2 | O(n(log n)2) |
| 100n log3 n + n3 + 100n | n3 | O(n3) |
Les instructions ci-dessous montrent quelques caractéristiques de la notation « Big-Oh » pour les fonctions f ≡ f (n) et g ≡ g (n). Déterminez si chaque instruction est TRUE ou FALSE et corrigez la formule dans ce dernier cas.
| Fonction | TRUE ou FALSE ? | Après correction |
| O(f + g) = O(f) + O(g) | FALSE | O(f + g) = max {O(f), O(g)} |
| O(f · g) = O(f) · O(g) | TRUE | |
| if g = O(f) and h = O(f) then g = O(h) | FALSE | if g = O(f) and f = O(h) then g = O(h) |
| 5n + 8n 2 + 100n 3 = O(n 4 ) | TRUE | |
| 5n+8n 2 +100n 3 = O(n 2 log n) | FALSE | O(n3 ) |
