Big-O — nommez la complexité du code
Lisez l'extrait, nommez sa complexité temporelle, puis regardez la courbe de croissance. Six classes, six manches. Gratuit.
Cinq extraits, cinq des six classes de complexité, chacune posée une fois.
Comment jouer
- Lisez l'extrait et choisissez sa complexité temporelle parmi les six.
- La courbe de croissance est tracée après chaque réponse : la vôtre en rouge, la bonne en vert.
- Cinq des six classes par partie, sans répétition : répondre toujours pareil est juste au plus une fois.
- Les bonnes réponses consécutives rapportent plus. Une mauvaise remet la série à zéro.
Comment ça marche
Chaque manche montre un court extrait de code et demande sa complexité temporelle. Vous répondez, et la courbe de croissance est tracée — la vôtre contre la bonne — si bien que le choix cesse d'être une étiquette et devient une forme que l'on voit. Une partie pose cinq des six classes, mélangées et sans répétition : répondre toujours la même chose est donc juste au plus une fois — et la classe écartée change, si bien que la dernière manche n'est jamais offerte par élimination. Les extraits sont choisis pour n'avoir qu'une réponse défendable : pas de sortie anticipée, pas de coût de bibliothèque caché, et rien qui livre sa propre complexité dans un commentaire. Le tri est pris comme O(n log n) partout, ce que fournit toute bibliothèque standard courante. Tout tourne sur votre appareil, rien n'est envoyé nulle part, et il n'y a aucun compte à créer.
La notation O décrit comment le coût croît, pas ce qu'il vaut. Un O(n²) aux bonnes constantes bat un O(n log n) alourdi aux tailles que voit la plupart du code réel — c'est le sujet d'un autre jeu de ce site.
Questions fréquentes
Pourquoi la courbe est-elle en échelle logarithmique ?
Parce que six classes ne tiennent pas autrement sur un même graphique. À n=24, une fonction à temps constant coûte 1 et une exponentielle seize millions : sur un axe linéaire, cinq des six courbes seraient la même ligne plate au fond. Une échelle logarithmique transforme chaque classe en une pente distinguable, et c'est cela qui mérite d'être vu.
Le tri est-il vraiment en O(n log n) ?
Pour les tris par comparaison, oui — c'est une borne inférieure démontrée, et c'est ce que fournit toute bibliothèque standard courante. Les tris par comptage et par base font mieux en ne comparant pas, mais exigent des hypothèses sur les clés. Quand un extrait appelle ici sort(), cela coûte n log n.
Pourquoi aucun extrait n'a de sortie anticipée ?
Parce qu'une sortie anticipée transforme un pire cas en cas moyen, et la réponse cesse d'être une classe unique. Une recherche linéaire qui retourne à la première correspondance est en O(n) au pire et en O(1) si la correspondance est toujours en tête : demander « la » complexité serait injuste. La recherche dichotomique est l'exception : elle sort tôt et reste exactement en O(log n).
La série compte-t-elle ?
Oui. Une bonne réponse sur deux consécutives augmente ce que rapporte la suivante, jusqu'à un plafond : une partie propre vaut donc nettement plus que quatre bonnes et deux mauvaises. Une mauvaise remet la série à zéro.