Recherche, tris et coût d'un algorithme

Tri fusion, Boyer-Moore et coûts : ce que la terminale ajoute aux tris et recherches vus en première.

NSI · fiche gratuite · 18 min de lecture

Ce qu'il faut savoir faire

Écrire les tris du programme, justifier un coût sans le calculer exactement, et prouver qu'une boucle fait ce qu'elle prétend faire.

Ce qui est un acquis de première, et ce que la terminale ajoute

Le programme de première contient « Tris par insertion, par sélection » et « Recherche dichotomique dans un tableau trié », avec l'invariant et le variant de boucle. Ces notions ne disparaissent pas : le programme de terminale annonce qu'« on continue l'étude de la notion de coût d'exécution, en temps ou en mémoire », et il y ajoute deux algorithmes nommément exigibles — le tri fusion, via la méthode « diviser pour régner », et la recherche textuelle, via l'algorithme de Boyer-Moore.

Autrement dit : réviser ce chapitre en s'arrêtant à la dichotomie et aux tris quadratiques, c'est réviser la première. Les deux dernières sections de cette fiche sont celles que l'épreuve de terminale peut demander directement.

Les coûts à connaître, sans hésitation

Algorithme	Au programme de	Meilleur cas	Pire cas	Ce qu'il exige
Recherche séquentielle	première	O(1)	O(n)	rien
Recherche dichotomique	première	O(1)	O(log n)	tableau trié
Tri par insertion	première	O(n)	O(n²)	rien
Tri par sélection	première	O(n²)	O(n²)	rien
Tri fusion	terminale	O(n log n)	O(n log n)	O(n) de mémoire en plus
Recherche naïve d'un motif	terminale	O(n)	O(n×m)	rien
Boyer-Moore	terminale	O(n/m)	O(n×m)	prétraitement du motif

Le tri par sélection cherche à chaque tour le minimum de la partie non triée : il fait toujours le même nombre de comparaisons, d'où l'absence de meilleur cas.

Ce que « O(n²) » veut dire concrètement

L'ordre de grandeur décrit comment le temps croît quand n grandit, pas le temps lui-même.

Doubler n multiplie par ~2 le temps d'un algorithme en O(n), par ~4 celui d'un O(n²).
Un O(n²) peut battre un O(n log n) sur de petites entrées : les constantes comptent, mais elles disparaissent de la notation.
Ce qu'on compte, ce sont les opérations élémentaires — comparaisons, affectations —, pas les secondes.

Invariant de boucle : la preuve attendue

Un invariant est une propriété vraie avant la boucle, conservée par chaque tour, et qui donne le résultat à la sortie.

Pour le tri par insertion : « après le tour i, les i+1 premières cases du tableau contiennent les i+1 premiers éléments initiaux, triés ». À la fin, i vaut n−1 : le tableau entier est trié. La rédaction attendue tient en trois phrases — initialisation, conservation, conclusion.

Terminaison : le variant

Pour une boucle `while`, exhibe une quantité entière, positive, qui décroît strictement à chaque tour : elle ne peut décroître indéfiniment, donc la boucle s'arrête. Dans la dichotomie, c'est la largeur `droite − gauche` de l'intervalle de recherche, divisée par deux à chaque tour.

Tri fusion : le tri de terminale

Le programme ne demande pas « un tri de plus » : il demande d'écrire un algorithme utilisant la méthode « diviser pour régner », et le tri fusion en est l'exemple canonique. Trois phases, toujours les mêmes :

Diviser — couper le tableau en deux moitiés.
Régner — trier chaque moitié par un appel récursif ; un tableau de taille 0 ou 1 est déjà trié, c'est le cas de base qui assure la terminaison.
Combiner — fusionner les deux moitiés triées en les parcourant en parallèle, en prenant à chaque tour le plus petit des deux éléments de tête.

D'où vient le O(n log n) — c'est la justification attendue, et elle tient les deux bouts : couper en deux à chaque appel donne log₂ n niveaux de récursion, et à chaque niveau les fusions traitent en tout les n éléments, soit O(n) par niveau. Le produit des deux donne n log n.

Ce qu'il coûte en échange : O(n) de mémoire supplémentaire — il ne trie pas en place, contrairement aux tris par insertion et par sélection. C'est le seul argument qui puisse encore faire préférer un tri quadratique. Et contrairement au tri par insertion, il n'a pas de meilleur cas : un tableau déjà trié se découpe et se fusionne exactement pareil.

Recherche textuelle : l'algorithme de Boyer-Moore

Capacité attendue, au mot près dans le programme de terminale : « Étudier l'algorithme de Boyer-Moore pour la recherche d'un motif dans un texte. » C'est la partie du chapitre la plus souvent sautée en révision, alors qu'elle y est nommée. Le problème : chercher un motif de longueur m dans un texte de longueur n.

La méthode naïve aligne le motif sur chaque position du texte et compare de gauche à droite : jusqu'à n−m+1 alignements × m comparaisons, soit O(n×m) dans le pire cas.

Boyer-Moore change deux choses, et ce sont les deux à retenir :

il compare le motif au texte de droite à gauche, en partant de la fin du motif ;
quand la comparaison échoue, il consulte une table de décalage calculée avant la recherche à partir du seul motif : si le caractère fautif du texte n'apparaît nulle part dans le motif, on décale de m d'un coup, sans jamais relire ces caractères.

Ce qu'il faut en dire à l'épreuve, sans le surestimer : le gain porte sur le cas moyen, qui devient sous-linéaire — on ne lit même pas tous les caractères du texte. Dans la version étudiée au lycée, le pire cas reste en O(n×m). Le prétraitement ne dépend que du motif, jamais du texte : on le paie une fois, on cherche ensuite autant de fois qu'on veut.

Comment justifier un coût en une phrase

Deux boucles imbriquées sur n : O(n²).
Une boucle qui divise n par 2 : O(log n).
Un parcours de graphe : O(sommets + arêtes) en listes d'adjacence.
Un appel de fonction dans une boucle : multiplie le coût de la fonction par le nombre de tours — l'oubli le plus fréquent.

Les erreurs qui coûtent le plus

Appliquer la dichotomie à un tableau non trié. Le résultat est faux, pas seulement lent.
Compter la complexité en secondes ou dépendre de la machine : on compte des opérations.
Confondre invariant (ce qui reste vrai) et variant (ce qui décroît et prouve l'arrêt).
Oublier le coût du tri préalable quand un énoncé trie pour pouvoir chercher ensuite.
Écrire « O(2n) » ou « O(n + 3) » : les constantes s'effacent, on écrit O(n).
Annoncer le tri fusion « en place » : il demande O(n) de mémoire en plus — c'est précisément son défaut.
Justifier son O(n log n) par « il divise par deux » seul : il faut les deux moitiés — log n niveaux et O(n) de fusion par niveau.
Croire que Boyer-Moore améliore le pire cas de la recherche naïve : il ne le garantit pas ; c'est le cas moyen qui s'effondre.
Prétraiter le texte au lieu du motif dans Boyer-Moore.

Vérifié le 13/10/2026 : ce chapitre figure au programme officiel de l’enseignement de spécialité de numérique et sciences informatiques de terminale (arrêté du 19-7-2019, NOR MENE1921247A, BO spécial n° 8 du 25 juillet 2019), rubrique « Algorithmique » — son annexe porte « On continue l’étude de la notion de coût d’exécution, en temps ou en mémoire », la capacité « Écrire un algorithme utilisant la méthode “diviser pour régner” » et « Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte ». Les tris par insertion et par sélection et la recherche dichotomique, eux, portent les mêmes intitulés dans l’annexe du programme de première — c’est le partage annoncé plus haut, et il est vérifié des deux côtés. L’épreuve, elle, est régie à compter de la session 2027 par la note de service du 11-9-2026 (NOR MENE2622643N, BO spécial n° 4 du 17 septembre 2026), qui porte sur « le programme de l’enseignement de spécialité de la classe de terminale en vigueur ».

Teste-toi — 7 questions corrigées

Réponds sans regarder la fiche : la correction et l'explication s'affichent après chaque réponse.

Si on double la taille des données, le temps d'un algorithme en O(n²) est multiplié par environ :

Réponse : 4. Le coût est proportionnel au carré : (2n)² = 4n². C'est exactement ce que la notation sert à prédire, sans jamais mesurer une seconde.
Le tri par sélection sur un tableau déjà trié effectue :

Réponse : le même nombre de comparaisons que sur un tableau quelconque. Il cherche le minimum de la partie non triée à chaque tour, quelle que soit la disposition initiale : son coût est en O(n²) dans tous les cas. Le tri par insertion, lui, profite d'un tableau déjà trié (O(n)).
Un variant de boucle sert à prouver :

Réponse : que la boucle s'arrête. Le variant est une quantité entière positive qui décroît strictement : elle ne peut décroître à l'infini, donc la boucle termine. La correction, elle, se prouve avec l'invariant.
La recherche dichotomique dans un tableau NON trié :

Réponse : peut renvoyer un résultat faux. Elle élimine une moitié en se fiant à l'ordre. Sans tri, l'élément cherché peut se trouver dans la moitié écartée : la réponse renvoyée est simplement fausse.
Le tri fusion est en O(n log n) parce que :

Réponse : découper en deux donne log n niveaux, et chaque niveau coûte O(n) de fusion. La justification attendue tient les deux bouts : log₂ n niveaux de récursion, et à chaque niveau les fusions traitent en tout les n éléments. Le tri fusion ne trie pas en place, et n'a pas de meilleur cas.
Comparé aux tris par insertion et par sélection, le tri fusion :

Réponse : demande O(n) de mémoire supplémentaire. C'est le prix du gain : il ne trie pas en place. Les tris quadratiques, eux, travaillent dans le tableau lui-même — c'est le seul argument qui puisse encore les faire préférer.
Dans l'algorithme de Boyer-Moore, la table de décalage est calculée à partir :

Réponse : du motif cherché, avant la recherche. Le prétraitement ne porte que sur le motif : on le paie une fois, puis on cherche dans autant de textes qu'on veut. C'est lui qui permet, en comparant de droite à gauche, de sauter jusqu'à m caractères d'un coup.

Cette fiche fait partie des 27 fiches de révision gratuites de RévizBac. Pour savoir où tu en es de ta moyenne et de ta mention, passe par le simulateur de note ; pour caser sa révision dans ta semaine, par le générateur de planning.

Autres fiches gratuites en NSI

Réussir les deux épreuves de NSI — Ce que valent l'écrit et la pratique, et ce que le correcteur attend exactement dans chaque cas.
Représentation binaire des données : entiers, flottants, textes, booléens — Prérequis de première : bases 2 et 16, complément à deux, bit à bit et débordement, flottants IEEE 754, ASCII, Unicode, UTF-8, De Morgan.

Avant l'épreuve : Méthode des épreuves de spécialité NSI — l'écrit, l'heure sur machine et la banque de sujets, en détail.