La notation Big-O décrit la tendance lorsque la quantité de données tend vers l'infini. Le problème, c'est que vos données réelles sont rarement proches de l'infini.
Qu'est-ce que la notation Big-O ne prend pas en compte ?
Cette notation omet délibérément les constantes et les termes d'ordre inférieur. Un algorithme 100n et un autre n sont tous deux de complexité O(n), même si le premier est cent fois plus lent quelle que soit la taille des données.
Exemple classique : tri d'un petit tableau
Le tri par insertion est de complexité O(n²), tandis que le tri par mélange est de complexité O(n log n). Pourtant, toutes les bibliothèques standard optent pour le tri par insertion lorsque le tableau compte moins de quelques dizaines d'éléments. La raison :
- L'ordre d'insertion est séquentiel, ce qui permet au cache du processeur de l'anticiper et évite pratiquement tout échec de prédiction
- Il ne nécessite pas d'allocation de mémoire auxiliaire
- La boucle est extrêmement simple et comporte peu d'instructions de branchement
Avec n = 20, la constante faible l'emporte nettement sur le taux de croissance.
La mémoire coûte plus cher que le calcul
Une opération d'addition prend moins d'une nanoseconde. Une lecture avec échec de cache nécessitant un accès à la RAM prend environ une centaine de nanosecondes. Cela signifie qu'un échec de cache équivaut à une centaine d'opérations arithmétiques.
C'est pourquoi la traversée d'un tableau contigu est généralement plus rapide que celle d'une liste chaînée, même si les deux sont de complexité O(n). Les éléments du tableau sont contigus en mémoire, et le processeur charge d'avance l'élément suivant ; dans une liste chaînée, en revanche, chaque nœud se trouve à un emplacement distinct.
Comment utiliser correctement la notation Big-O
- Utilisez-le pour éliminer d'emblée les mauvaises conceptions — un temps d'exécution O(n²) sur un million d'éléments ne fait aucun doute
- Ne l’utilisez pas pour choisir entre deux options de même complexité — effectuez des mesures
- Demandez-vous toujours quelle est la taille réelle des données, car elle est souvent inférieure à ce que vous imaginez
Thảo luận