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.

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.

À ne pas confondre sur les tris et le coût

AlgorithmeConditionCoût
Recherche dichotomiqueListe triéeO(log n)
Tri par insertionAucuneO(n²) au pire
Tri fusionAucuneO(n log n)
Chargement gloutonTri préalable par ratio prix/volumeCoût du tri (quadratique avec insertion)

Mode Bac : ce qui rapporte des points

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.

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).

  1. 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.
  2. 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.
  3. Tour 2: liste[5] = 'nathan' est après 'lea' : fin = 4, m = (4 + 4) // 2 = 4.
  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).
  5. 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.
  6. 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.

Comment réviser le coût, les tris et la recherche ?

  1. Écrire de mémoire le tri par insertion: Avec une boucle for et une boucle while. Vérifiez sur [4, 2, 3, 1].
  2. Écrire la dichotomie: En itératif avec deb, fin, m, puis en renvoyant l'indice ou -1.
  3. Apprendre le tableau des coûts: O(1), O(log n), O(n), O(n log n), O(n²) avec un exemple pour chacun.
  4. Savoir prouver la terminaison: Trouver un variant et expliquer en trois lignes pourquoi il décroît.
  5. 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