Explorateur de complexité Big-O

Le Big-O décrit comment le travail croît lorsque la taille d'entrée augmente. Une simple boucle croît à peu près avec N, les boucles imbriquées croissent souvent avec N², et la récursion ramifiée peut croître exponentiellement. La leçon importante est l'échelle : pour un petit N, de nombreuses approches se ressemblent, mais pour un N plus grand, la classe de croissance domine le temps d'exécution.

La façon la plus claire de ressentir une classe de croissance est de doubler l'entrée et d'observer ce qui arrive au travail. En O(log N), il bouge à peine — la recherche dichotomique trouve un élément parmi un million en environ 20 comparaisons. En O(N), le travail double, et en O(N²) il quadruple. Faites glisser N dans cet outil et voyez les écarts passer d'invisibles à écrasants.

Une classe de croissance plus basse ne garantit pas un programme plus rapide. Les informaticiens appellent ces exceptions des algorithmes galactiques : des méthodes à meilleure notation Big-O dont le facteur constant caché est si énorme qu'elles ne dépassent les méthodes simples que sur des entrées plus grandes que tout ce que contient l'univers physique. Plusieurs algorithmes record de multiplication matricielle ne sont jamais utilisés pour cette raison précise — Big-O écarte discrètement les constantes qui décident de la vitesse réelle.