Algorithmique — Complexité et algorithmes fondamentaux
Programme en vigueur — arrêtés du 17 janvier 2019, applicable en Première depuis la rentrée 2019. Voir le texte
Notion de complexité temporelle : O(1), O(n), O(n²), O(log n). Algorithmes de tri : insertion, sélection, fusion (merge sort), rapide (quicksort). Recherche dichotomique. Algorithme de Dijkstra (introduction).
La règle d'or
La complexité mesure la croissance du coût quand la taille de l'entrée augmente : c'est une loi d'évolution, pas une durée en secondes.
L'erreur que tout le monde fait
Appliquer une recherche dichotomique à un tableau qui n'a pas été trié au préalable.
La dichotomie élimine la moitié des éléments à chaque étape en supposant que tout ce qui est à gauche est plus petit et tout ce qui est à droite plus grand. Sans tri, cette hypothèse est fausse et l'algorithme renvoie une absence pour une valeur pourtant présente, sans jamais signaler d'erreur.
Avant d'écrire une dichotomie, vérifier dans l'énoncé que le tableau est trié, et sinon compter le coût du tri.
Sur mille éléments, un algorithme quadratique fait un million d'opérations là où une recherche dichotomique en fait dix. L'écart n'est pas une question de machine rapide ou lente : c'est une loi de croissance, et aucun processeur ne la rattrape. Savoir la calculer, c'est savoir quel programme tiendra quand les données grossiront.
1Ce que mesure la complexité
Règle
La complexité mesure la croissance du coût quand la taille de l'entrée augmente : c'est une loi d'évolution, pas une durée en secondes. On la note O(n) et on ignore les constantes multiplicatives et les termes de moindre ordre, parce qu'ils cessent de compter quand l'entrée grandit. Les classes usuelles, par coût croissant : O(1), O(log n), O(n), O(n log n), O(n²).
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)
Piège
Comparer deux algorithmes par leur temps mesuré sur un petit jeu de données.
Pourquoi — Sur une petite entrée, les constantes dominent : un algorithme quadratique bien optimisé peut battre un algorithme en O(n log n) mal implémenté. Mais l'ordre s'inverse nécessairement à partir d'une certaine taille, et l'écart devient ensuite irrattrapable. Un chronomètre sur mille éléments ne dit rien du comportement sur un million.
Le réflexe — Comparer des lois de croissance, pas des mesures ponctuelles.
Exemple
Comparer le nombre d'opérations d'un algorithme en O(n²) et d'une recherche par dichotomie, pour n = 1 000.
Pour l'algorithme quadratique, l'ordre de grandeur est n × n :1000×1000=1000000
Soit environ un million d'opérations.
La dichotomie divise l'espace de recherche par deux à chaque étape : il faut environ dix étapes, puisque 2 puissance 10 dépasse 1 000.2×2×2×2×2×2×2×2×2×2=1024
Soit dix opérations contre un million : le rapport est de cent mille.
Environ 1 000 000 contre 10
2La recherche dichotomique
Règle
La dichotomie cherche une valeur en comparant à l'élément central : si la valeur cherchée est plus petite, on élimine toute la moitié droite, sinon la moitié gauche. Chaque comparaison divise par deux l'espace restant, d'où une complexité en O(log n). Elle exige une condition impérative : le tableau doit être trié.
chaqueeˊtapedivisel′espacederecherchepar2
Piège
Appliquer une recherche dichotomie à un tableau qui n'a pas été trié au préalable.
Pourquoi — L'algorithme élimine une moitié sur la seule foi de la comparaison centrale. Sans tri, rien ne garantit que la valeur cherchée ne s'y trouvait pas : l'algorithme ne plante pas, il répond simplement « absent » pour un élément présent. C'est une faute silencieuse, qui ne se manifeste que par des résultats faux sur certaines entrées.
Le réflexe — Avant toute dichotomie, vérifier — ou établir — que le tableau est trié.
3Les tris
Propriété
Le tri par insertion construit la partie triée élément par élément, en insérant chaque nouvel élément à sa place. Sa complexité est en O(n²) dans le cas défavorable, mais il est efficace sur de petits tableaux et sur des données presque triées. Le tri fusion applique le principe « diviser pour régner » : couper le tableau en deux, trier chaque moitié, puis fusionner les deux moitiés triées. Sa complexité est en O(n log n) dans tous les cas.
Le tri fusion illustre ce qu'apporte la récursivité : la fusion de deux listes déjà triées est facile, et c'est cette facilité qu'on obtient en découpant. Il a un coût que le tri par insertion n'a pas : il utilise de la mémoire supplémentaire pour la fusion. Choisir un tri, c'est donc arbitrer entre temps et mémoire, et non désigner un vainqueur absolu.
4Les graphes
Propriété
L'algorithme de Dijkstra calcule le plus court chemin depuis un sommet de départ dans un graphe dont les arêtes portent des poids positifs. Son principe : maintenir pour chaque sommet la meilleure distance connue, traiter à chaque étape le sommet non traité le plus proche, et mettre à jour ses voisins. La condition de positivité n'est pas un détail : avec des poids négatifs, l'algorithme peut figer une distance qu'un chemin ultérieur aurait améliorée.
Évaluer la complexité d'un algorithme
Identifier la taille de l'entrée, notée n : nombre d'éléments, de sommets, de caractères.
Repérer les boucles et leur imbrication : deux boucles imbriquées sur n donnent O(n²).
Repérer les découpages par deux : ils introduisent un logarithme.1000×1000=1000000Deux boucles imbriquées sur 1 000 éléments donnent un million d'opérations.
Ignorer les constantes et les termes dominés : O(3n + 5) s'écrit O(n).
Conclure en précisant s'il s'agit du cas favorable, moyen ou défavorable.
▢Ai-je identifié la taille de l'entrée avant de compter ?
▢Ai-je compté l'imbrication des boucles, et non leur nombre ?
▢Ai-je ignoré les constantes dans ma notation ?
▢Ai-je précisé le cas — favorable, moyen, défavorable ?
▢Mon tableau est-il trié avant toute dichotomie ?
▢Ai-je vérifié que les poids sont positifs avant d'appliquer Dijkstra ?
L'essentiel en 11 points
·La complexité est une loi de croissance, pas une durée.
·O(1) < O(log n) < O(n) < O(n log n) < O(n²).
·Ignorer les constantes : O(3n + 5) s'écrit O(n).
·Boucles imbriquées sur n : O(n²). Découpage par deux : logarithme.
·La dichotomie exige un tableau trié — sinon faute silencieuse.
·Chaque étape de dichotomie divise par deux l'espace de recherche.
·Tri par insertion : O(n²) au pire, efficace sur petit ou presque trié.
·Tri fusion : O(n log n) dans tous les cas, au prix de mémoire supplémentaire.
·Dijkstra : plus court chemin, à condition de poids positifs.
·Comparer des lois, jamais des chronomètres sur petites entrées.
·Aucun algorithme n'est meilleur dans l'absolu : tout dépend du contexte.
2
Imprimer
Fiche PDF — Algorithmique — Complexité et algorithmes fondamentaux
Gratuit · sans compte
Trois documents à imprimer, 6 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.
c.Quelle condition la recherche dichotomique exige-t-elle ?
d.Quelle est la complexité du tri fusion ? Du tri par insertion dans le cas défavorable ?
e.Que calcule l'algorithme de Dijkstra ? Sous quelle condition ?
›Voir le corrigéMasquer le corrigé
a. La croissance du coût quand la taille de l'entrée augmente. Non : c'est une loi d'évolution, pas une durée en secondes.
b. O(1), O(log n), O(n), O(n log n), O(n²).
c. Que le tableau soit trié.
d. Le tri fusion est en O(n log n) dans tous les cas ; le tri par insertion en O(n²) dans le cas défavorable.
e. Le plus court chemin depuis un sommet de départ, à condition que les arêtes portent des poids positifs.
2
Comparer les ordres de grandeur. On raisonne en nombre d'opérations.
Calculer
a.Combien d'opérations pour un algorithme en O(n²) avec n = 1 000 ?
b.Combien d'étapes pour une dichotomie sur 1 000 éléments ?
c.Calculer le rapport entre les deux.
d.Si n passe à 2 000, par combien le coût quadratique est-il multiplié ?
e.Et le coût de la dichotomie ?
›Voir le corrigéMasquer le corrigé
a. Ordre de grandeur :1000×1000=1000000
Soit environ un million d'opérations.
b. Environ dix, puisque dix divisions par deux couvrent plus de mille éléments :2×2×2×2×2×2×2×2×2×2=1024
c. Rapport :1000000÷10=100000
Soit cent mille fois plus d'opérations.
d. Le coût est multiplié par quatre : doubler n multiplie n² par 2 × 2.2×2=4
e. Il augmente d'une seule étape : passer de 1 000 à 2 000 demande une division par deux supplémentaire. C'est toute la différence entre une loi quadratique et une loi logarithmique.
3
Un développeur applique une recherche dichotomique à un tableau non trié. Analyser.
Analyser
a.Le programme va-t-il planter ?
b.Que va-t-il renvoyer pour un élément pourtant présent ?
c.Pourquoi cette faute est-elle plus dangereuse qu'une erreur qui interrompt le programme ?
d.Faut-il trier avant de chercher ? Dans quel cas est-ce rentable ?
›Voir le corrigéMasquer le corrigé
a. Non. L'algorithme compare, élimine une moitié et termine normalement : rien dans son déroulement ne signale l'anomalie.
b. Il peut renvoyer « absent » alors que l'élément est présent : il l'a éliminé avec une moitié sur la foi d'une comparaison qui ne voulait rien dire.
c. Parce qu'elle est silencieuse : un plantage se voit et se corrige, un résultat faux se propage. Le programme continue, et l'erreur n'apparaît que sur certaines entrées — donc parfois jamais pendant les tests.
d. Trier coûte O(n log n), chercher une fois en O(n) sans tri. Pour une seule recherche, le tri n'est pas rentable. Il le devient dès qu'on effectue de nombreuses recherches sur le même tableau : le coût du tri est payé une fois, chaque recherche coûte ensuite O(log n).
4
Choisir un algorithme. Raisonner.
Raisonner
a.Pourquoi comparer deux algorithmes sur un petit jeu de données est-il trompeur ?
b.Dans quel cas le tri par insertion est-il préférable au tri fusion ?
c.Quel coût le tri fusion a-t-il que le tri par insertion n'a pas ?
d.Pourquoi Dijkstra échoue-t-il avec des poids négatifs ?
e.Que signifie qu'il n'existe pas de « meilleur algorithme » dans l'absolu ?
›Voir le corrigéMasquer le corrigé
a. Parce que sur une petite entrée, les constantes dominent : un algorithme quadratique bien optimisé peut battre un O(n log n) mal implémenté. L'ordre s'inverse nécessairement au-delà d'une certaine taille.
b. Sur de petits tableaux et sur des données presque triées, où il est très efficace — c'est d'ailleurs pourquoi certains tris performants l'emploient sur les petits fragments.
c. De la mémoire supplémentaire pour la fusion : il n'opère pas sur place.
d. Parce qu'il fige la distance d'un sommet dès qu'il le traite, en supposant qu'aucun chemin ultérieur ne pourra faire mieux. Avec un poids négatif, un détour peut réduire la distance après coup, et l'hypothèse tombe.
e. Que le choix dépend de contraintes : taille des données, mémoire disponible, état initial des données, nombre de recherches à effectuer. Un algorithme est adapté à un contexte, et annoncer un vainqueur sans préciser lequel revient à répondre à une question qu'on n'a pas posée.
Ce qui rapporte des points, ce qui en coûte
Définir la complexité comme loi de croissance4 ptsPerdu si : La confondre avec un temps d'exécution
Déduire une complexité de l'imbrication des boucles4 ptsPerdu si : Compter le nombre de boucles au lieu de leur imbrication
Exiger un tableau trié pour la dichotomie5 ptsPerdu si : L'appliquer à un tableau quelconque
Comparer les tris selon leurs contraintes4 ptsPerdu si : Désigner un tri vainqueur absolu
Énoncer la condition de Dijkstra3 ptsPerdu si : L'appliquer à des poids négatifs
4
La méthode
Évaluer la complexité d'un algorithme
1
Nommer la grandeur qui mesure la taille de l'entrée.
2
Repérer les boucles et leur imbrication, puis compter les opérations élémentaires.
3
Déterminer si le nombre d'étapes double, se multiplie ou se divise lorsque l'entrée double.
Diviser l'espace de recherche par deux à chaque tour donne un coût logarithmique.
4
Distinguer le meilleur cas, le cas moyen et le pire cas quand ils diffèrent.
5
Conclure par l'ordre de grandeur dominant, en écartant les constantes et les termes négligeables.
5
Se tester
Touches 1 à 4
NSIPremière
Question 1
Pour tester la robustesse du système de communication de la sonde Juno en orbite autour de Jupiter, l'équipe simule un bug dans une fonction Python qui calcule la distance parcourue par la sonde en fonction de sa vitesse et du temps écoulé. Voici le code buggé :
```python
def calcul_distance(vitesse, temps):
distance = 0
for i in range(temps):
distance += vitesse
return distance
```
Quel est le bug dans ce code et comment le corriger ?
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Algorithmique — Complexité et algorithmes fondamentaux : c'est en quelle classe ?+
Ce chapitre est au programme de NSI au lycée, en classe de Première, année du Bac de français. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
Que faut-il savoir sur Algorithmique — Complexité et algorithmes fondamentaux ?+
Notion de complexité temporelle : O(1), O(n), O(n²), O(log n). Algorithmes de tri : insertion, sélection, fusion (merge sort), rapide (quicksort). Recherche dichotomique. Algorithme de Dijkstra (introduction). Les notions à maîtriser sont : complexité, tri par insertion, tri fusion, dichotomie, Dijkstra, O(n).
Où télécharger la fiche PDF de Algorithmique — Complexité et algorithmes fondamentaux ?+
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 6 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Le corrigé de Algorithmique — Complexité et algorithmes fondamentaux est-il fourni ?+
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Algorithmique — Complexité et algorithmes fondamentaux peut-il tomber au Bac de français ?+
Ce chapitre fait partie du programme officiel de Première, il entre donc dans le périmètre du Bac de français. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Comment réviser Algorithmique — Complexité et algorithmes fondamentaux efficacement ?+
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Faut-il un compte pour s'entraîner sur Algorithmique — Complexité et algorithmes fondamentaux ?+
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.
Notions voisines
Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.