Comportement asymptotique.
Estimer la performance d'un algorithme en fonction de la taille de ses entrées (n).
Une complexité peut être :
Une complexité est généralement représentée sous forme d'Ordre de grandeur, noté O.
| Complexité | Notation (n) | Exemple | |
|---|---|---|---|
| Constante | O(1) | Accès tableau | |
| Logarithmique | O(log(n)) | Dichotomie (meilleurs tris, arbres équilibrés) | |
| Linéaire | O(n) | Parcours de liste | |
| Quasi-linéaire (ou linéarithmique ou loglinéaire) | O(n.log(n)) | Transformation fast fourrier | |
| Polynomiale | Quadratique | O(n2) | |
| Cubique | O(n3) | ||
| Polynomiale | O(ne) | ||
| Sous-exponentielle | O(nlog(n)) | ||
| Polylogarithmique | O(log(n)e) | ||
| Exponentielle | O(en) | ||
| Factorielle | O(n!) | ||