Comment utiliser cette calculatrice
- Saisissez la taille d’entrée n attendue à une échelle réaliste.
- Sélectionnez la classe de complexité de votre algorithme.
- Comparez le nombre d’opérations à celui des autres classes.
- Estimez le temps réel d’exécution en divisant par un nombre plausible d’opérations par seconde.
Méthode de calcul
Les classes de complexité se classent selon leur taux de croissance : O(1) constante, O(log n) logarithmique, O(n) linéaire, O(n log n) linéarithmique, O(n²) quadratique, O(2ⁿ) exponentielle et O(n!) factorielle. Les constantes et les termes d’ordre inférieur sont négligés, car ils cessent d’être déterminants lorsque n augmente. 3n² + 500n est en O(n²), car au-delà d’une certaine taille, le terme au carré domine tous les autres.
La conséquence pratique est une rupture brutale, pas une pente progressive. À n = 1,000, un algorithme quadratique nécessite un million d’opérations, ce qui est instantané ; à n = 1,000,000, il en nécessite mille milliards, ce qui prend des heures. C’est pourquoi le tri est en O(n log n) et les recherches par hachage en O(1). Les classes sont choisies pour que dix fois plus de données ne signifie pas cent fois plus de travail. Pour les petites valeurs de n, les constantes déterminent réellement le gagnant, ce qui explique pourquoi les implémentations de tri passent au tri par insertion en dessous d’un certain seuil.
Formule et références
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Analyse asymptotique standard (notation grand O) telle que définie dans Cormen et al., Introduction to Algorithms.
Exemple de calcul
Comparaison d’une boucle imbriquée en O(n²) avec un tri en O(n log n) pour n = 250,000.
- O(n²) = 250,000² = 6.25 × 10¹⁰ opérations.
- O(n log n) = 250,000 × log₂(250,000) ≈ 250,000 × 18 = 4.5 × 10⁶.
- Rapport ≈ 13,900×.
- À 10⁸ ops/seconde : 625 secondes contre 0.045 seconde.
Dix minutes contre un vingtième de seconde, pour la même tâche, avec pour seule différence le choix de l’algorithme.
Questions fréquentes
La notation grand O donne-t-elle le temps d’exécution réel ?
Non. Elle décrit la croissance. Une routine en O(n) avec une constante élevée peut être plus lente qu’une routine légère en O(n log n) sur de petites tailles.
Pourquoi ignorer les constantes ?
Parce qu’elles ne changent pas la courbe de croissance, qui détermine si l’algorithme reste utilisable lors du passage à l’échelle.
Et la complexité spatiale ?
C’est la même notation appliquée à la mémoire. Un tri en place utilise O(1) d’espace auxiliaire ; le tri fusion utilise O(n).
O(n log n) est-il le meilleur résultat possible pour le tri ?
Pour le tri par comparaison, oui. Les tris par comptage et par base font mieux en exploitant la structure des clés plutôt que des comparaisons.