Coût des algorithmes, tris et recherche (Bac NSI)
Mis à jour le · AprenAI
Ce thème réunit les tris, la recherche dichotomique et l'analyse de leur coût. Dans les annales digitalisées du Bac NSI, il compte 3 sujets (2021, 2024 et 2025), de 2,25 à 3 points chacun : un tri par insertion, un algorithme glouton de chargement de marchandises et une recherche dichotomique. À chaque fois, il faut compléter du code, nommer l'algorithme et justifier son coût.
- 23 sujets officiels
- 4,6 % des sujets
- 2021-2026 années
Quelles notions maîtriser sur les tris, la recherche et le coût ?
Le coût d'un algorithme se mesure en nombre d'opérations élémentaires (comparaisons, décalages) en fonction de la taille n des données. On donne un ordre de grandeur : constant O(1), logarithmique O(log n), linéaire O(n), quasi-linéaire O(n log n), quadratique O(n²). On l'évalue souvent dans le pire des cas.
Le tri par insertion parcourt la liste et insère chaque élément à sa place parmi les éléments déjà triés à sa gauche. Pour l'élément d'indice i, on initialise j = i, puis tant que j > 0 et que l'élément précédent doit passer après l'élément courant, on décale et on décrémente j (j = j - 1), puis on place l'élément en position j. Dans le sujet 2025, on trie une collection de papillons selon pap['taille'] et la fonction renvoie la liste triée. Son coût est quadratique : dans le pire cas (liste triée à l'envers), l'élément d'indice i demande i comparaisons et i décalages, soit 1 + 2 + ... + (n-1) = n(n-1)/2 opérations, de l'ordre de n².
La recherche dichotomique cherche un élément dans une liste triée en comparant avec l'élément du milieu, puis en éliminant la moitié des éléments. Dans le sujet 2021, rechercheDicho(elem, liste) utilise deb = 0, fin = len(liste) - 1 et m = (deb + fin) // 2, et boucle tant que deb <= fin : si liste[m] == elem, elle renvoie True ; si liste[m] > elem, fin = m - 1 ; sinon deb = m + 1. Elle ne s'applique que si le tableau est trié. Son coût est logarithmique, O(log n), car l'intervalle est divisé par 2 à chaque tour. La terminaison se prouve avec un variant de boucle : l'entier fin - deb reste positif ou nul tant que la boucle tourne et décroît strictement à chaque itération qui ne renvoie pas True, donc il finit par devenir strictement négatif.
Un algorithme glouton choisit à chaque étape l'option localement la meilleure sans revenir en arrière. Dans le sujet 2024, ChargementGlouton trie les marchandises par prix volumique (ratio prix/volume) décroissant et charge celles qui rentrent. Avec m1 = (40, 20), m2 = (210, 70), m3 = (160, 40), m4 = (50, 50) pour 100 litres, le tri donne m3, m2, m1, m4 et l'algorithme charge m3 et m1 pour 200 €, alors que la meilleure combinaison est m1 et m2 pour 250 € (90 litres). Le glouton n'est donc pas toujours optimal. Enfin, l'algorithme des k plus proches voisins (k-NN) du sujet 2025 classe une donnée en calculant sa distance à toutes les données déjà classées, en retenant les k plus proches et en choisissant la classe majoritaire parmi elles.
- Coût (complexité): Ordre de grandeur du nombre d'opérations d'un algorithme en fonction de la taille n des données.
- Tri par insertion: Tri qui insère chaque élément à sa place dans la partie déjà triée. Coût quadratique dans le pire des cas.
- Recherche dichotomique: Recherche dans une liste triée qui divise l'intervalle par deux à chaque étape. Coût en O(log n).
- Variant de boucle: Entier positif qui décroît strictement à chaque tour et prouve la terminaison.
- Algorithme glouton: Algorithme qui fait à chaque étape le choix localement optimal, sans retour en arrière.
- k plus proches voisins: Méthode de classification qui attribue à une donnée la classe majoritaire de ses k voisines les plus proches.
À ne pas confondre sur les tris et le coût
- Recherche séquentielle ≠ Recherche dichotomique: La séquentielle parcourt la liste, coût O(n), sans exiger qu'elle soit triée ; la dichotomique est en O(log n) mais exige une liste triée.
- Pire des cas ≠ Cas favorable: Pour le tri par insertion, la liste déjà ordonnée coûte peu ; la liste triée à l'envers donne n(n-1)/2 opérations.
- Glouton ≠ Optimal: Le glouton donne une solution rapide mais pas forcément la meilleure : 200 € contre 250 € dans le sujet 2024.
- Variant ≠ Invariant: Le variant décroît et prouve la terminaison ; un invariant reste vrai à chaque tour et prouve la correction.
- O(log n) ≠ O(n): Doubler la taille ajoute une étape pour la dichotomie, mais double le travail d'une recherche linéaire.
| Algorithme | Condition | Coût |
|---|---|---|
| Recherche dichotomique | Liste triée | O(log n) |
| Tri par insertion | Aucune | O(n²) au pire |
| Tri fusion | Aucune | O(n log n) |
| Chargement glouton | Tri préalable par ratio prix/volume | Coût du tri (quadratique avec insertion) |
Mode Bac : ce qui rapporte des points
- Nom de l'algorithme: « Tri par insertion », « algorithme glouton », « recherche dichotomique » : le nom exact est demandé dans les questions courtes.
- Pire cas du tri par insertion: Liste triée dans l'ordre inverse : n(n-1)/2 opérations, donc coût quadratique O(n²).
- Coût de la dichotomie: Logarithmique, O(log n), car la taille est divisée par 2 à chaque étape ; le tableau doit être trié.
- Variant: fin - deb : entier naturel tant que deb <= fin, strictement décroissant, donc la boucle termine.
- Principe de k-NN: Distances à toutes les données, sélection des k plus petites, classe majoritaire.
- Trace de la dichotomie: Tableau des colonnes deb, fin, m à chaque tour.
Quels sujets sont tombés sur le coût, les tris et la recherche ?
Dans les annales digitalisées, 3 sujets relèvent du thème : 2021, 2024 et 2025, tous en Métropole. Ils pèsent 2,75, 3 et 2,25 points. Aucun ne demande de démontrer un coût en toute généralité : on attend un ordre de grandeur justifié par un raisonnement court.
- Compléter un tri par insertion (2): Compléter les lignes du tri (j = i, comparaison de pap['taille'], j = j - 1, return collec) puis nommer l'algorithme et son coût (Métropole France 1 remplacement, 2025, exercice 3) ; même démarche sur la classe Marchandise avec tri sur ratio() (Métropole France 2, 2024, exercice 2, partie B).
- Algorithme glouton de chargement: Lister les combinaisons possibles pour 100 litres, trouver la meilleure (m1 et m2, 250 €), nommer l'algorithme glouton et écrire la fonction charge (Métropole France 2, 2024, exercice 2, partie B).
- Recherche dichotomique (1): Vrai ou faux sur le tri préalable, coût, variant fin - deb, trace avec Lnoms, renvoi de l'indice (Métropole France 1 remplacement, 2021, exercice 2).
- Principe de l'algorithme k-NN: Expliquer en quelques lignes comment classer un papillon non identifié (2025, exercice 3).
- Exercice 3 - Tri et coût des algorithmes · Métropole 1 remplacement 2025 · Compléter un tri par insertion
- Exercice 2 - Partie B · Métropole 2024 (sujet 2) · Compléter un tri par insertion
- Exercice 2 - Partie B · Métropole 2024 (sujet 2) · Algorithme glouton de chargement
- Exercice 2 - Recherche dichotomique · Métropole 1 remplacement 2021 · Recherche dichotomique
- Exercice 3 - Tri et coût des algorithmes · Métropole 1 remplacement 2025 · Principe de l'algorithme k-NN
Entraîne-toi : Coût des algorithmes, tris et recherche (23 sujets officiels)
Tous les sujets de NSI sur « Coût des algorithmes, tris et recherche » (2021-2026), avec le corrigé.
Comment tracer la dichotomie et justifier un coût ?
Exemple : Métropole France 1 remplacement, 2021, exercice 2. Lnoms = ["alice", "bob", "etienne", "hector", "lea", "nathan", "paul"], on trace rechercheDicho("lea", Lnoms).
- Initialiser: deb = 0, fin = len(liste) - 1 = 6 et non 6 écrit en dur : fin = 6 ne conviendrait qu'à une liste de 7 éléments. m = (0 + 6) // 2 = 3.
- Tour 1: liste[3] = 'hector' est avant 'lea' dans l'ordre alphabétique : on passe dans le else, deb = 4, m = (4 + 6) // 2 = 5.
- Tour 2: liste[5] = 'nathan' est après 'lea' : fin = 4, m = (4 + 4) // 2 = 4.
- Tour 3: liste[4] = 'lea' : égalité, la fonction renvoie True. Le tableau de trace contient (0, 6, 3), (4, 6, 5), (4, 4, 4).
- Justifier la terminaison: v = fin - deb est un entier naturel tant que deb <= fin ; si liste[m] > elem, fin diminue ; sinon deb augmente. Dans les deux cas v décroît strictement : la boucle s'arrête.
- Justifier le coût: L'intervalle de recherche est divisé par 2 à chaque tour : le nombre d'étapes est proportionnel à log₂ n, donc O(log n).
Quelles erreurs éviter sur le coût des algorithmes ?
Les corrigés sont des réponses types sans barème détaillé. On y lit ce qui doit figurer dans la copie : un nom exact, un ordre de grandeur et une justification.
- Oublier de nommer le pire cas: Pour le tri par insertion, précisez : liste triée dans l'ordre inverse de celui voulu, avec i comparaisons et i décalages pour l'élément d'indice i.
- Écrire fin = 6: Utilisez len(liste) - 1 : le code doit fonctionner pour toute liste.
- Utiliser la dichotomie sur une liste non triée: La propriété « tableau trié » est indispensable : c'est la première question vrai/faux du sujet 2021.
- Mal choisir le sens de la comparaison dans un tri: Dans le tri sur ratio(), l'ordre est décroissant : on compare marchandise.ratio() > tab[j].ratio().
- Penser que le glouton est toujours optimal: L'exemple 2024 le contredit : 200 € contre 250 €.
- Confondre j - 1 et j + 1: Dans le tri par insertion, on remonte vers la gauche : j décroît.
Comment réviser le coût, les tris et la recherche ?
- Écrire de mémoire le tri par insertion: Avec une boucle for et une boucle while. Vérifiez sur [4, 2, 3, 1].
- Écrire la dichotomie: En itératif avec deb, fin, m, puis en renvoyant l'indice ou -1.
- Apprendre le tableau des coûts: O(1), O(log n), O(n), O(n log n), O(n²) avec un exemple pour chacun.
- Savoir prouver la terminaison: Trouver un variant et expliquer en trois lignes pourquoi il décroît.
- Refaire les trois sujets officiels: Dichotomie 2021, glouton 2024 et tri 2025, puis un sujet complet de Métropole.
Quelle est la complexité du tri par insertion ?
Elle est quadratique, O(n²), dans le pire des cas. Si la liste est triée à l'envers, l'élément d'indice i demande i comparaisons et i décalages, soit n(n-1)/2 opérations au total.
Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?
Parce qu'elle élimine la moitié des éléments en comparant avec la valeur du milieu. Cette élimination n'est correcte que si les éléments sont ordonnés.
Comment prouver la terminaison de la recherche dichotomique ?
Avec le variant fin - deb : c'est un entier positif tant que la boucle tourne, et il diminue strictement à chaque itération, donc il devient négatif et la boucle s'arrête.
Un algorithme glouton donne-t-il toujours la meilleure solution ?
Non. Dans le sujet 2024, le glouton charge deux marchandises pour 200 € alors qu'une autre combinaison rapporte 250 €.
Comment fonctionne l'algorithme des k plus proches voisins ?
On calcule la distance entre la nouvelle donnée et toutes les données classées, on garde les k plus proches et on lui attribue la classe majoritaire parmi elles.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets