La notation big O
En maths : f(n) = O(g(n)) est une notation exprimant que le rapport f(n)/g(n) est borné,
On utilise fréquemment cette notation à propos de la complexité en temps d'un algorithme,
Exemples les plus courants :
| Notation |
Complexité |
Exemple |
| O(1) |
constante |
calcul simple sur un jeu de données |
| O(log(n)) |
logarithmique |
la recherche dichotomique |
| O(n) |
complexité |
un parcours de tableau |
| O(n log(n)) |
linéarithmique |
tri par tas |
| O(n²) |
quadratique |
2 boucles imbriqués sur un tableau |
Références
Explication sur la compléxité en temps
Complexité en temps sur les objets Python