Aller au contenu
Ludicademy
Français
Thème Élan
ClairsSombres
S’inscrire
Tle · Algorithmique

La complexité : compter les opérations, pas les secondes

ce qui se passe quand les données deviennent grandes

≈ 4 min de lecture · palier Tle · trois questions à la fin

Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode

En bref
  • La complexité compte les opérations selon la taille n, pas les secondes sur une machine
  • On garde l'ordre de grandeur : le terme dominant, sans ses constantes
  • Deux boucles imbriquées sur les mêmes données donnent du n au carré

Le chronomètre est un mauvais juge

Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change. La COMPLEXITÉ répond autrement : elle compte le NOMBRE D'OPÉRATIONS effectuées en fonction de la taille des données, notée n. C'est une propriété de l'algorithme, pas de l'ordinateur qui l'exécute.

On ne cherche pas un nombre exact. On cherche l'ORDRE DE GRANDEUR : ce qui arrive au temps de calcul quand n double. C'est la seule information qui survit au changement de machine, et c'est celle qui décide si un programme tiendra sur des données réelles.

Les cinq familles qu'on rencontre

La familleLa notationQuand n doubleExemple typique
ConstanteO(1)Rien ne changeLire le premier élément d'une liste
LogarithmiqueO(log n)Une opération de plusLa recherche dichotomique
LinéaireO(n)Le temps doubleLe parcours complet d'une liste
QuadratiqueO(n²)Le temps quadrupleLe tri par sélection, deux boucles imbriquées
ExponentielleO(2 puissance n)Le temps est mis au carréL'essai de toutes les combinaisons

Compter, sur un cas concret

La méthode est mécanique : on repère les boucles, on regarde combien de tours chacune fait, et l'on multiplie les boucles imbriquées.Algorithme du tri par sélection. La boucle extérieure fait n moins 1 passes. À la passe numéro i, la boucle intérieure compare les n moins i éléments restants. Le total vaut n moins 1, plus n moins 2, plus… plus 1 : c'est la somme des premiers entiers, soit n fois n moins 1, divisé par deux. Développons : la moitié de n au carré, moins la moitié de n. Quand n vaut 1 000, le premier terme vaut 500 000 et le second 500 : le second est mille fois plus petit, et il le sera de plus en plus. On le laisse tomber, ainsi que le facteur un demi, et l'on écrit O(n²). Ce n'est pas de la négligence : on affirme exactement ce qui compte, à savoir que doubler n multiplie le travail par quatre.

Une complexité meilleure ne garantit pas un programme plus rapide SUR LES PETITES DONNÉES. Un O(n log n) avec de lourdes constantes peut perdre contre un O(n²) simple jusqu'à quelques dizaines d'éléments — c'est pourquoi les bibliothèques de tri réelles basculent sur un tri par insertion sous un certain seuil. La complexité décrit une TENDANCE, pas une promesse à chaque taille.

Ce que cela permet de décider avant d'écrire

Un algorithme exponentiel sur trente données demande déjà un milliard d'opérations : il est inutilisable, et aucune machine plus rapide ne le sauvera, car ajouter une seule donnée double le travail. Savoir cela AVANT d'écrire évite de passer une semaine à optimiser ce qui ne peut pas l'être — et oriente vers un autre algorithme, ou vers une réponse approchée assumée.

SkeletMon programme trie mille éléments en une seconde. C'est excellent.
OscarCombien pour dix mille ?
SkeletDix secondes, j'imagine. Dix fois plus.
OscarVotre tri est quadratique. Cent secondes. Et pour cent mille, deux heures et demie.
SkeletJ'aurais préféré ne pas savoir.
OscarVous l'auriez su. Plus tard, et en production.
À retenir
  • La complexité compte les opérations selon la taille n, pas les secondes sur une machine
  • On garde l'ordre de grandeur : le terme dominant, sans ses constantes
  • Deux boucles imbriquées sur les mêmes données donnent du n au carré
  • Une complexité exponentielle est condamnée dès quelques dizaines de données
Exercice

Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ?

n est multiplié par dix, donc n au carré par cent. Le temps suit le carré, pas la taille.

Exercice

Que signifie O(log n) quand la taille des données double ?

Doubler n ajoute un seul niveau de division par deux : c'est ce qui rend la dichotomie si économique.

Expressions à emporter

Expression Traduction
complexitéle nombre d'opérations selon la taille
ordre de grandeurle terme dominant, sans constantes
quadratiquedoubler n multiplie le travail par quatre

Maintenant, jouez-la

Trois questions pour voir

La règle est lue. Voyons si elle est entrée : trois questions, ici même, sans compte.

7 exercices corrigés de logique en Tle → sans compte, corrigés à chaque réponse

La règle est lue ; il reste à la faire entrer. Trois minutes suffisent.

Jouer « le pont de cordes » → Quiz Express · sans compte

Ou choisissez votre salle :

Et côté jeux de société : 🎪 Échecs → les règles d'échecs

Sur papier : 🖨️ La fiche de cette leçon

Pour réviser : 📝 La fiche de révision et celle du chapitre « algorithmique » (3 leçons)

Toutes les leçons Tle