Avec un système de pièces fictif composé de 1, 3 et 4, que donne l'algorithme glouton pour rendre 6 ?

3 pièces (4 + 1 + 1), alors que l'optimum est de 2 pièces (3 + 3)

2 pièces, ce qui est optimal, car l'algorithme choisit toujours la meilleure combinaison

3 pièces, et c'est optimal, puisqu'aucune combinaison ne fait mieux

4 pièces (1 + 1 + 1 + 3), un résultat pourtant loin d'être optimal

Quel est le comportement du tri rapide (quicksort) dans le pire des cas ?

O(n²), lorsque le pivot choisi est systématiquement le plus petit ou le plus grand élément

O(n log n), tout comme sa complexité moyenne, sans aucun mauvais cas

O(log n), comme pour une recherche dans un arbre binaire équilibré

O(n), comme pour un simple parcours linéaire de tout le tableau entier

Comment fonctionne un algorithme glouton ?

Il construit la solution étape par étape en faisant à chaque fois le choix qui paraît le meilleur sur le moment, sans jamais revenir dessus

Il explore toutes les solutions possibles avant de choisir la meilleure

Il revient en arrière dès qu'il constate une erreur

Il trie systématiquement les données puis renvoie le premier élément

Quelles sont les trois étapes de la méthode « diviser pour régner » ?

Diviser le problème en sous-problèmes, résoudre chaque sous-problème, combiner les résultats

Diviser le résultat par deux, arrondir, vérifier

Pourquoi le tri fusion relève-t-il de la méthode « diviser pour régner » ?

Parce qu'il coupe le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les résultats

Parce qu'il divise chaque valeur du tableau par deux

Parce qu'il compare les éléments deux à deux

Parce qu'il utilise une pile pour mémoriser les échanges

Algorithmes gloutons et diviser pour régner

Terminale · NSI · Algorithmique

Algorithmique

Les algorithmes gloutons

Certains problèmes demandent de trouver la meilleure solution parmi un nombre gigantesque de possibilités : rendre la monnaie avec le moins de pièces, remplir un sac à dos pour maximiser la valeur emportée, planifier le maximum de réunions dans une salle. Examiner toutes les combinaisons est souvent hors de portée. L'approche gloutonne propose un compromis : décider vite, quitte à ne pas toujours décider juste.

Exemple de référence : le rendu de monnaie
Problème : rendre une somme donnée avec le moins de pièces possible. Le critère glouton naturel : prendre à chaque étape la plus grande pièce qui ne dépasse pas ce qu'il reste à rendre.

Deuxième exemple : le problème du sac à dos
On dispose d'objets ayant chacun une masse et une valeur, et d'un sac de capacité limitée. Objectif : maximiser la valeur emportée sans dépasser la capacité.

Critères gloutons possibles : prendre d'abord les objets les plus précieux, ou les plus légers, ou — le plus pertinent — ceux dont le rapport valeur/masse est le plus élevé. Aucun de ces trois critères ne garantit l'optimum lorsque les objets sont indivisibles : c'est un problème réputé difficile.

	Algorithme glouton	Recherche exhaustive (force brute)
Principe	un choix localement optimal à chaque étape	on énumère toutes les solutions possibles
Retour en arrière	jamais	systématique
Coût typique	faible : souvent O(n) ou O(n log n) avec un tri préalable	exponentiel : 2^n combinaisons pour n objets
Résultat	une solution valide, pas toujours optimale	l'optimum garanti
Quand l'utiliser	grandes instances, quand une bonne solution suffit	petites instances, quand l'optimum est indispensable

Concevoir et évaluer un algorithme glouton

Étape 1 — Identifie ce qu'il faut optimiser : un minimum (nombre de pièces) ou un maximum (valeur emportée).
Étape 2 — Choisis un critère de sélection explicite : la plus grande pièce, le meilleur rapport valeur/masse, la réunion qui finit le plus tôt…
Étape 3 — Trie les candidats selon ce critère si nécessaire — c'est souvent le terme dominant du coût, en O(n log n).
Étape 4 — Parcours les candidats une seule fois : prends chacun s'il est compatible avec les contraintes, ignore-le sinon. Ne reviens jamais en arrière.
Étape 5 — Justifie ou réfute l'optimalité. Pour prouver que le glouton N'EST PAS optimal, un seul contre-exemple bien choisi suffit : c'est ce qu'attend l'épreuve.
Étape 6 — Conclus toujours en indiquant si ta solution est optimale, ou seulement approchée.

Algorithmique

Diviser pour régner

L'autre grande stratégie du programme repose sur une idée que tu utilises sans le savoir quand tu cherches un mot dans un dictionnaire papier : plutôt que de tout lire, on coupe le problème en deux. Répétée, cette opération transforme des coûts linéaires en coûts logarithmiques — un gain spectaculaire sur de grandes données.

La recherche dichotomique
Objectif : chercher une valeur dans un tableau trié. On regarde l'élément du milieu : s'il est égal à la valeur cherchée, c'est fini ; s'il est plus grand, la valeur ne peut se trouver que dans la moitié gauche ; s'il est plus petit, dans la moitié droite. À chaque comparaison, on élimine la moitié du tableau.

Coût : le nombre d'étapes est le nombre de fois qu'on peut diviser n par 2 avant d'arriver à 1, c'est-à-dire environ log2(n) : la complexité est en O(log n). Sur un tableau d'un million d'éléments, cela fait au plus 20 comparaisons au lieu d'un million.

Le tri fusion
Le tri fusion est l'application emblématique de la méthode :
Diviser — couper le tableau en deux moitiés de tailles égales (à un élément près).
Régner — trier récursivement chaque moitié ; un tableau de 0 ou 1 élément est déjà trié, c'est le cas de base.
Combiner — fusionner les deux moitiés triées en un seul tableau trié, en comparant à chaque fois leurs deux premiers éléments restants.

La fusion de deux tableaux triés totalisant n éléments coûte O(n) : chaque élément n'est examiné qu'une fois. Comme il y a environ log2(n) niveaux de découpage et que chaque niveau coûte O(n) au total, la complexité est en O(n log n) — et ce dans tous les cas, ce qui est une garantie précieuse.

Algorithme	Stratégie	Complexité	Remarque
Recherche séquentielle	parcours simple	O(n)	fonctionne sur un tableau non trié
Recherche dichotomique	diviser pour régner	O(log n)	exige un tableau TRIÉ
Tri par sélection / insertion	itératif	O(n²)	simple mais inutilisable sur de grandes données
Tri fusion	diviser pour régner	O(n log n) dans tous les cas	nécessite un tableau auxiliaire, donc O(n) de mémoire
Tri rapide (quicksort)	diviser pour régner	O(n log n) en moyenne, O(n²) au pire	trie en place ; le pire cas vient d'un pivot mal choisi

Reconnaître et analyser un algorithme « diviser pour régner »

Étape 1 — Repère l'appel récursif portant sur une entrée de taille strictement plus petite : sans lui, ce n'est pas diviser pour régner.
Étape 2 — Identifie le cas de base, celui qui arrête la récursion (tableau vide ou à un seul élément, intervalle de recherche vide).
Étape 3 — Compte le nombre de sous-problèmes et leur taille : UN sous-problème de taille n/2 pour la dichotomie, DEUX pour le tri fusion.
Étape 4 — Évalue le coût de l'étape de combinaison : O(1) pour la dichotomie (il n'y a rien à recombiner), O(n) pour la fusion du tri fusion.
Étape 5 — Écris la relation de récurrence. Dichotomie : C(n) = C(n/2) + 1, ce qui donne O(log n). Tri fusion : C(n) = 2 × C(n/2) + n, ce qui donne O(n log n).
Étape 6 — Vérifie toujours ton résultat sur un petit cas concret, n = 8 par exemple, en dessinant l'arbre des appels.

Exercices corrigés

À quelle condition la recherche dichotomique est-elle applicable ?
- A.À n'importe quel tableau
- B.À une liste chaînée
- C.À un tableau triéBonne réponse
- D.À un dictionnaire
Réponse : C — À un tableau trié
Toute la méthode repose sur une déduction : si l'élément du milieu est plus grand que la valeur cherchée, alors celle-ci ne peut se trouver qu'à gauche. Ce raisonnement n'est valable que si le tableau est TRIÉ. Sur une liste chaînée, il manquerait de plus l'accès direct par indice : atteindre le milieu coûterait déjà O(n). Et un dictionnaire n'a pas besoin de dichotomie, son hachage lui donne déjà un accès en O(1).
Avec le système de pièces euro (1, 2, 5, 10, 20, 50 centimes), combien de pièces l'algorithme glouton utilise-t-il pour rendre 37 centimes ?
- A.3
- B.6
- C.5
- D.4Bonne réponse
Réponse : D — 4
Déroulons le glouton : la plus grande pièce ≤ 37 est 20, il reste 17 ; la plus grande ≤ 17 est 10, il reste 7 ; la plus grande ≤ 7 est 5, il reste 2 ; enfin la pièce de 2 solde le compte. Total : 20 + 10 + 5 + 2 = 37, soit 4 pièces. Vérifie toujours ta somme ! Ici le glouton est aussi optimal, car le système euro est canonique — mais ce n'est pas une propriété générale des systèmes de pièces.
Avec un système de pièces fictif composé de 1, 3 et 4, que donne l'algorithme glouton pour rendre 6 ?
- A.2 pièces, ce qui est optimal, car l'algorithme choisit toujours la meilleure combinaison
- B.3 pièces, et c'est optimal, puisqu'aucune combinaison ne fait mieux
- C.3 pièces (4 + 1 + 1), alors que l'optimum est de 2 pièces (3 + 3)Bonne réponse
- D.4 pièces (1 + 1 + 1 + 3), un résultat pourtant loin d'être optimal
Réponse : C — 3 pièces (4 + 1 + 1), alors que l'optimum est de 2 pièces (3 + 3)
Le glouton prend d'abord la plus grande pièce possible, 4 : il reste 2, qu'il ne peut solder qu'avec deux pièces de 1. Total : 4 + 1 + 1 = 6, soit 3 pièces. Or 3 + 3 = 6 n'en demande que 2. Le glouton s'est piégé lui-même : ayant pris 4, il ne revient jamais dessus. C'est LE contre-exemple à connaître, celui qui prouve qu'un algorithme glouton donne une solution valide sans être nécessairement optimale.
Combien de niveaux de découpage le tri fusion effectue-t-il sur un tableau de 8 éléments ?
- A.8
- B.3Bonne réponse
- C.4
- D.2
Réponse : B — 3
Suivons les tailles successives : 8 se coupe en deux tableaux de 4 (niveau 1), chacun en deux tableaux de 2 (niveau 2), chacun en deux tableaux de 1 (niveau 3). Trois découpages suffisent, ce qui correspond à log2(8) = 3. Répondre 4 revient à compter aussi le tableau initial comme un niveau de découpage. C'est la profondeur de récursion, et elle explique directement le facteur log n de la complexité.
Quel est le comportement du tri rapide (quicksort) dans le pire des cas ?
- A.O(n log n), tout comme sa complexité moyenne, sans aucun mauvais cas
- B.O(n²), lorsque le pivot choisi est systématiquement le plus petit ou le plus grand élémentBonne réponse
- C.O(log n), comme pour une recherche dans un arbre binaire équilibré
- D.O(n), comme pour un simple parcours linéaire de tout le tableau entier
Réponse : B — O(n²), lorsque le pivot choisi est systématiquement le plus petit ou le plus grand élément
Le tri rapide partitionne le tableau autour d'un pivot. Si le pivot est bien centré, les deux parties sont équilibrées et l'on obtient O(n log n). Mais si le pivot est à chaque fois le minimum ou le maximum, une des deux parties est vide et l'autre contient n − 1 éléments : la récursion atteint alors n niveaux coûtant chacun O(n), soit O(n²). Cela arrive typiquement quand on prend le premier élément comme pivot sur un tableau déjà trié. C'est la différence majeure avec le tri fusion, garanti en O(n log n) quoi qu'il arrive.
Comment fonctionne un algorithme glouton ?
- A.Il explore toutes les solutions possibles avant de choisir la meilleure
- B.Il revient en arrière dès qu'il constate une erreur
- C.Il trie systématiquement les données puis renvoie le premier élément
- D.Il construit la solution étape par étape en faisant à chaque fois le choix qui paraît le meilleur sur le moment, sans jamais revenir dessusBonne réponse
Réponse : D — Il construit la solution étape par étape en faisant à chaque fois le choix qui paraît le meilleur sur le moment, sans jamais revenir dessus
Le glouton est myope par construction : il optimise localement, à chaque étape, selon un critère fixé, et il ne remet jamais en cause un choix passé. C'est ce qui le rend rapide — mais aussi ce qui l'empêche parfois d'atteindre l'optimum. L'exploration exhaustive (option 1) et le retour en arrière (option 2) décrivent d'autres stratégies, bien plus coûteuses. Un tri préalable est fréquent, mais ce n'est qu'un moyen, pas la définition.
Quelles sont les trois étapes de la méthode « diviser pour régner » ?
- A.Trier, chercher, afficher
- B.Diviser le problème en sous-problèmes, résoudre chaque sous-problème, combiner les résultatsBonne réponse
- C.Tester, corriger, recommencer
- D.Diviser le résultat par deux, arrondir, vérifier
Réponse : B — Diviser le problème en sous-problèmes, résoudre chaque sous-problème, combiner les résultats
Les trois temps sont toujours les mêmes : DIVISER en sous-problèmes de même nature mais plus petits, RÉGNER en les résolvant (le plus souvent par appel récursif, jusqu'à un cas de base), puis COMBINER les solutions partielles. Ce schéma se reconnaît dans la recherche dichotomique, le tri fusion et le tri rapide. Attention au faux ami de l'option 4 : ce n'est pas le résultat qu'on divise, c'est le PROBLÈME.
Quelle est la complexité de la recherche dichotomique dans un tableau de n éléments ?
- A.O(log n)Bonne réponse
- B.O(n)
- C.O(n log n)
- D.O(1)
Réponse : A — O(log n)
À chaque comparaison, la zone de recherche est divisée par deux. Le nombre d'étapes correspond donc au nombre de fois qu'on peut diviser n par 2 avant d'atteindre 1, soit environ log2(n) : la complexité est logarithmique. O(n) serait le coût d'une recherche séquentielle. Et le coût n'est pas constant : chercher dans un tableau d'un milliard d'éléments demande une trentaine de comparaisons, contre une dizaine pour mille éléments.
Quelle est la complexité du tri fusion ?
- A.O(n²)
- B.O(n log n)Bonne réponse
- C.O(n)
- D.O(log n)
Réponse : B — O(n log n)
Le tri fusion découpe le tableau en deux jusqu'aux éléments isolés : cela crée environ log2(n) niveaux. À chaque niveau, les fusions traitent au total les n éléments, pour un coût O(n). Le produit donne O(n log n), et ce dans TOUS les cas — c'est une garantie que le tri rapide n'offre pas. O(n²) correspond aux tris élémentaires (sélection, insertion), et aucun tri par comparaisons ne peut descendre sous O(n log n).
Combien de comparaisons au maximum une recherche dichotomique effectue-t-elle dans un tableau trié de 1000 éléments ?
- A.Environ 10Bonne réponse
- B.Environ 100
- C.1000
- D.Environ 500
Réponse : A — Environ 10
À chaque comparaison, la zone restante est divisée par deux : 1000, puis 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. On atteint 1 en une dizaine d'étapes, ce que confirme le calcul 2^10 = 1024 ≥ 1000. Répondre 500 correspondrait au nombre MOYEN de comparaisons d'une recherche séquentielle, et 1000 à son pire cas. Retiens l'ordre de grandeur : multiplier la taille du tableau par 1000 n'ajoute que 10 comparaisons.
Dans le tri fusion, quel est le coût de la fusion de deux tableaux triés totalisant n éléments ?
- A.O(1)
- B.O(n)Bonne réponse
- C.O(n²)
- D.O(log n)
Réponse : B — O(n)
La fusion avance de front dans les deux tableaux : à chaque tour, on compare les deux plus petits éléments restants et on recopie le plus petit dans le résultat. Chaque élément n'est donc examiné et recopié qu'une seule fois, d'où un coût linéaire O(n). C'est précisément cette efficacité qui rend le tri fusion performant : un coût de combinaison plus élevé ferait grimper la complexité totale au-delà de O(n log n).
Pourquoi le tri fusion relève-t-il de la méthode « diviser pour régner » ?
- A.Parce qu'il divise chaque valeur du tableau par deux
- B.Parce qu'il compare les éléments deux à deux
- C.Parce qu'il utilise une pile pour mémoriser les échanges
- D.Parce qu'il coupe le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les résultatsBonne réponse
Réponse : D — Parce qu'il coupe le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les résultats
On retrouve les trois étapes canoniques : DIVISER (couper le tableau en deux moitiés), RÉGNER (trier chaque moitié par appel récursif, jusqu'au cas de base d'un tableau à 0 ou 1 élément), COMBINER (fusionner les deux moitiés triées). L'option 1 confond diviser le PROBLÈME et diviser les VALEURS. Comparer deux à deux est le propre de tout tri par comparaisons, et ce n'est pas une pile explicite qui est en jeu ici, mais la récursion.

S'entraîner sur ce chapitre

Ce chapitre compte 36 exercices corrigés dans l'application, avec le suivi de ta progression.

Commencer les exercices